蓝桥杯178 全球变暖

[复制链接]
发表于 2025-7-25 23:38:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
标题描述

你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示&#xff
1a;
.......
.##....
.##....
....##.
..####.
...###.
.......
此中"上下左右"四个方向上连在一起的一片陆地构成一座岛屿。比方上图就有 2 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。详细来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
比方上图中的海域未来会变成如下样子&#xff
1a;
.......
.......
.......
.......
....#..
.......
.......
请你盘算&#xff
1a;依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入描述

第一行包含一个整数 N (
1≤N≤
1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第
1 行、第
1 列、第 N 行、第 N 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例

示例

输入
  1. 7
  2. .......
  3. .##....
  4. .##....
  5. ....##.
  6. ..####.
  7. ...###.
  8. .......
复制代码
输出
  1. 1
复制代码
 
 难。。
[list=
1]
  •         遍历整个网格&#xff
    1a;

    •                 遇到未被访问的陆地 (i,j)(c[j] &#6
      1;&#6
      1; '#' && mem[j] &#6
      1;&#6
      1; 0),说明发现新岛屿。
           
  •         DFS 探索该岛屿&#xff
    1a;

    •                 递归访问所有相连的陆地。
    •                 统计该岛屿中 不会被淹没的陆地数量 flag。
    •                 判断陆地是否会被淹没
    •                 陆地淹没规则&#xff
      1a;如果一块陆地 四周至少有一个海洋('.'),它就会被淹没。

      •                         在 dfs(x,y) 中,cnt统计 (x,y) 四周的陆地数量。
      •                         如果 cnt&#6
        1;&#6
        1; 4(即四全面是陆地),则 (x,y) 不会被淹没 → falg++。
                     
           
  •         判断岛屿是否完全淹没&#xff
    1a;

    •                 如果 flag&#6
      1;&#6
      1; 0(岛屿中没有不会被淹没的陆地),则 ans++(该岛屿会被完全淹没)。
           
    1. #include<iostream>using namespace std;const int N &#6
    2. 1;
    3. 1e3+
    4. 10;int n;char c[N][N];int mem[N][N];int dx[4] &#6
    5. 1; {0, 0, -
    6. 1,
    7. 1};int dy[4] &#6
    8. 1; {-
    9. 1,
    10. 1, 0, 0};int flag;  //统计当前岛屿中不会被淹没的陆地数量int ans;  //统计会被完全淹没的岛屿数量void dfs(int x, int y){        int cnt&#6
    11. 1;0;  //统计当前陆地四周的陆地数量                for(int i&#6
    12. 1;0; i<4; i++)        {                int nx&#6
    13. 1;x+dx[i];                int ny&#6
    14. 1;y+dy[i];                                if(nx<
    15. 1 || ny<
    16. 1 || nx>n || ny>n) continue;  //越界                 if(c[nx][ny]&#6
    17. 1;&#6
    18. 1;'.')  //如果是海洋                {                        mem[nx][ny]&#6
    19. 1;
    20. 1;                         continue;                }                                if(c[nx][ny]&#6
    21. 1;&#6
    22. 1;'#')   //如果是陆地                {                        cnt++;  //增加四周陆地计数                        if(mem[nx][ny]&#6
    23. 1;&#6
    24. 1;0)                        {                                mem[nx][ny]&#6
    25. 1;
    26. 1;                                dfs(nx, ny);                        }                 }                        }        //如果当前陆地四周都是陆地,增加不会被淹没的陆地数量        if(cnt&#6
    27. 1;&#6
    28. 1;4) flag++;}int main(){        cin>>n;        for(int i&#6
    29. 1;
    30. 1; i<&#6
    31. 1;n; ++i)        {                for(int j&#6
    32. 1;
    33. 1; j<&#6
    34. 1;n; ++j)                {                        cin>>c[i][j];                }        }                 for(int i&#6
    35. 1;
    36. 1; i<&#6
    37. 1;n; ++i)        {                for(int j&#6
    38. 1;
    39. 1; j<&#6
    40. 1;n; ++j)                {                        //如果当前位置是陆地且未被访问(说明这块陆地属于一个新的岛屿)                         if(c[i][j]&#6
    41. 1;&#6
    42. 1;'#' && mem[i][j]&#6
    43. 1;&#6
    44. 1;0)                        {                                flag&#6
    45. 1;0;  //重新统计该岛屿中不会被淹没的陆地数量                                 dfs(i, j);                                if(flag&#6
    46. 1;&#6
    47. 1;0) ans++;  //如果岛屿中不会被淹没的陆地为0,说明会被完全淹没                        }                }        }                 cout<<ans;                return 0;}
    复制代码
    免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao
    123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
    继续阅读请点击广告
  • 回复

    使用道具 举报

    快速回复 返回顶部 返回列表