你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
....... .##.... .##.... ....##. ..####. ...###. .......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
....... ....... ....... ....... ....#.. ....... .......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
输出
一个整数表示答案。
样例输入 Copy
7 ....... .##.... .##.... ....##. ..####. ...###. .......
这道题可以用dfs深搜来做,先找到每一个岛屿,然后搜索这个岛屿是否存在有无法被淹没的点,如果找到,则该岛屿无法被湮没
#include<iostream> #include<cstring> #include<queue> using namespace std; const int N = 1000; char map[N][N]; int n; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int cnt = 0; bool flag = false; int ans = 0; int res_ans = 0; void dfs(int x,int y) { //该点在岛屿上 if (map[x][y] != '#') { return ; } //不越界 if (x > n || x < 0 || y > n || y < 0) { return ; } //判断是否为无法淹没的点 if (flag == false) { cnt = 0; for(int i = 0;i < 4;i++) { int tx = x + dx[i]; int ty = y + dy[i]; //检验边界条件,该点是否可达 if (tx < n && tx >= 0 && ty < n && ty >= 0 && map[tx][ty] != '.') { cnt++; } } if (cnt == 4) { ans++; //如果找到一个无法被淹没的点,就停止搜索该岛屿 flag = true; } } //防止重复遍历一个点 map[x][y] = '*'; //dfs搜索 for(int i = 0;i < 4;i++) { int tx = x + dx[i]; int ty = y + dy[i]; dfs(tx,ty); } } int main() { cin >> n; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { cin >> map[i][j]; } } //找到每一个岛屿 for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if (map[i][j] == '#') { res_ans++; flag = false; dfs(i,j); } } } cout << res_ans - ans << endl; }
标签:map,tx,ty,int,.......,蓝桥,++,全球,变暖 From: https://www.cnblogs.com/polang19/p/17074023.html