马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?立即注册
×
标题描述
你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示ÿ
1a;
.......
.##....
.##....
....##.
..####.
...###.
.......
此中"上下左右"四个方向上连在一起的一片陆地构成一座岛屿。比方上图就有 2 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。详细来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
比方上图中的海域未来会变成如下样子ÿ
1a;
.......
.......
.......
.......
....#..
.......
.......
请你盘算ÿ
1a;依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 N (
1≤N≤
1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第
1 行、第
1 列、第 N 行、第 N 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例
示例
输入- 7
- .......
- .##....
- .##....
- ....##.
- ..####.
- ...###.
- .......
复制代码 输出
难。。
[list=
1]
遍历整个网格ÿ
1a;
- 遇到未被访问的陆地 (i,j)(c[j] 
1;
1; '#' && mem[j] 
1;
1; 0),说明发现新岛屿。
DFS 探索该岛屿ÿ
1a;
- 递归访问所有相连的陆地。
- 统计该岛屿中 不会被淹没的陆地数量 flag。
- 判断陆地是否会被淹没
- 陆地淹没规则ÿ
1a;如果一块陆地 四周至少有一个海洋('.'),它就会被淹没。
- 在 dfs(x,y) 中,cnt统计 (x,y) 四周的陆地数量。
- 如果 cnt
1;
1; 4(即四全面是陆地),则 (x,y) 不会被淹没 → falg++。
判断岛屿是否完全淹没ÿ
1a;
- 如果 flag
1;
1; 0(岛屿中没有不会被淹没的陆地),则 ans++(该岛屿会被完全淹没)。
- #include<iostream>using namespace std;const int N 
- 1;
- 1e3+
- 10;int n;char c[N][N];int mem[N][N];int dx[4] 
- 1; {0, 0, -
- 1,
- 1};int dy[4] 
- 1; {-
- 1,
- 1, 0, 0};int flag; //统计当前岛屿中不会被淹没的陆地数量int ans; //统计会被完全淹没的岛屿数量void dfs(int x, int y){ int cnt
- 1;0; //统计当前陆地四周的陆地数量 for(int i
- 1;0; i<4; i++) { int nx
- 1;x+dx[i]; int ny
- 1;y+dy[i]; if(nx<
- 1 || ny<
- 1 || nx>n || ny>n) continue; //越界 if(c[nx][ny]
- 1;
- 1;'.') //如果是海洋 { mem[nx][ny]
- 1;
- 1; continue; } if(c[nx][ny]
- 1;
- 1;'#') //如果是陆地 { cnt++; //增加四周陆地计数 if(mem[nx][ny]
- 1;
- 1;0) { mem[nx][ny]
- 1;
- 1; dfs(nx, ny); } } } //如果当前陆地四周都是陆地,增加不会被淹没的陆地数量 if(cnt
- 1;
- 1;4) flag++;}int main(){ cin>>n; for(int i
- 1;
- 1; i<
- 1;n; ++i) { for(int j
- 1;
- 1; j<
- 1;n; ++j) { cin>>c[i][j]; } } for(int i
- 1;
- 1; i<
- 1;n; ++i) { for(int j
- 1;
- 1; j<
- 1;n; ++j) { //如果当前位置是陆地且未被访问(说明这块陆地属于一个新的岛屿) if(c[i][j]
- 1;
- 1;'#' && mem[i][j]
- 1;
- 1;0) { flag
- 1;0; //重新统计该岛屿中不会被淹没的陆地数量 dfs(i, j); if(flag
- 1;
- 1;0) ans++; //如果岛屿中不会被淹没的陆地为0,说明会被完全淹没 } } } cout<<ans; return 0;}
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao
123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
|