oa系统网站建设方案/好网站制作公司

  原题地址:1.岛屿个数 - 蓝桥云课

问题描述

小蓝得到了一副大小为 M×NM×N 的格子地图，可以将其视作一个只包含字符 '0'（代表海水）和 '1'（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 '1' 相连接而形成。

在岛屿 AA 所占据的格子中，如果可以从中选出 kk 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),…,(xk−1,yk−1)(x0​,y0​),(x1​,y1​),…,(xk−1​,yk−1​)，其中 (xi+1modk,yi+1modk)(xi+1modk​,yi+1modk​) 是由 (xi,yi)(xi​,yi​) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)(0≤i≤k−1)，此时这 kk 个格子就构成了一个“环”。如果另一个岛屿 BB 所占据的格子全部位于这个“环”内部，此时我们将岛屿 BB 视作是岛屿 AA 的子岛屿。若 BB 是 AA 的子岛屿，CC 又是 BB 的子岛屿，那 CC 也是 AA 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

输入格式

第一行一个整数 TT，表示有 TT 组测试数据。

接下来输入 TT 组数据。对于每组数据，第一行包含两个用空格分隔的整数 MM、NN 表示地图大小；接下来输入 MM 行，每行包含 NN 个字符，字符只可能是 '0' 或 '1'。

输出格式

对于每组数据，输出一行，包含一个整数表示答案。

样例输入

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

样例输出

1
3

        这个题同时用了dfs和bfs，首先先用bfs将将所有不同的岛屿进行染色操作，用于区分各个岛屿。其次每一次将一个岛屿染色后都要紧接着从该岛屿的首格出发向周围的八个方向，进行dfs深度搜索 。如果某一条路线上碰到了别的岛屿就结束当前的递归，如果出现了某一条路径可以抵达grid的边界，那么就证明该岛屿并没有被其他岛屿；因为如果该岛屿被其他岛屿包围，当dfs遍历到其他岛屿时就会结束递归，就不可能到达grid的边界。

具体代码如下:

#include <iostream>
#include <vector>
#include <cstring>
#define PII pair<char,char>
using namespace std;int row,col;
int cnt = 0;
int dic[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int dict[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
char grid[55][55];
bool visited[55][55];
PII q[2550];//模拟队列
void bfs(int x,int y){int front = 0,rear = 0;//队头和队尾q[rear++] = {x,y};grid[x][y] = '1' + cnt;//染色操作while (front < rear){PII t = q[front++];//取出队头坐标for (int i = 0;i < 4;++i){//将队头坐标的四个方向的合法坐标依次入队int xx = t.first + dic[i][0];int yy = t.second + dic[i][1];if (xx >= 0 && xx < row && yy >= 0 && yy < col){if (grid[xx][yy] == '1'){grid[xx][yy] = '1' + cnt;q[rear++] = {xx,yy};}}}}
}
bool dfs(int x,int y){//当在某一个方向可以到达边界时，就证明该岛屿并没有被其他岛屿所包围if (x == 0 || x == row - 1 || y == 0 || y == col - 1)return true;visited[x][y] = true;for (int i = 0;i < 8;++i){int xx = x + dict[i][0];int yy = y + dict[i][1];//'1' + cnt为当前岛屿所染的色if (!visited[xx][yy] && (grid[xx][yy] == '0' || grid[xx][yy] == '1' + cnt)){//当前位置是海，或者没有到其他岛屿的范围就继续搜索if (dfs(xx,yy))return true;}}return false;
}
int main()
{int t;cin>>t;for (int i = 0;i < t;++i){int res = 0;cin>>row>>col;for (int j = 0;j < row;++j){cin>>grid[j];}cnt = 1;//从第一个岛屿开始，将第一个岛屿染色为cnt + 1for (int j = 0;j < row;++j){for (int k = 0;k < col;++k){if (grid[j][k] == '1'){//进行染色操作bfs(j,k);//初始化visited数组memset(visited,0,sizeof(visited));if (dfs(j,k))//从点(j,k)开始向八个方向进行寻找，看是否能到达边界，是的话就证明该岛屿并没有被某个岛屿完全包围res++;cnt++;}}}cout<<res<<endl;}return 0;
}