网站建设怎么跑业务,赣县城乡规划建设局网站,wordpress仪表盘加载很慢,巨野做网站小蓝得到了一副大小为 M N 的格子地图#xff0c;可以将其视作一个只包含字符‘0’#xff08;代表海水#xff09;和 ‘1’#xff08;代表陆地#xff09;的二维数组#xff0c;地图之外可以视作全部是海水#xff0c;每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’…小蓝得到了一副大小为 M × N 的格子地图可以将其视作一个只包含字符‘0’代表海水和 ‘1’代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中如果可以从中选出 k 个不同的格子使得他们的坐标能够组成一个这样的排列(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)其中(x(i1)%k , y(i1)%k) 是由 (xi , yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)
此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。
输入格式
第一行一个整数 T表示有 T 组测试数据。
接下来输入 T 组数据。对于每组数据第一行包含两个用空格分隔的整数M、N 表示地图大小接下来输入 M 行每行包含 N 个字符字符只可能是‘0’ 或 ‘1’。
输出格式
对于每组数据输出一行包含一个整数表示答案。
#include iostream
#include queue
using namespace std;
typedef pairint, intpii; //结果提二维
const int N 100;
int n, m;
int g[N][N]; //模拟二维图bool st_sea[N][N]; //是否走过海
bool st_road[N][N]; //是否走过陆地int dsx[8] { -1,-1, -1,0,1,1,1,0}; //海的8个方向遍历
int dsy[8]{-1,0,1,1,1,0,-1,-1};int drx[4] { -1,0,1,0 }; //陆地的4个方向编列
int dry[4] { 0,1,0,-1 };int ans0;
void bfs_road(int x, int y);
bool check(int x,int y)
{return (x 0 x n y 0 y m);}void bfs_sea(int x,int y)
{st_sea[x][y] true; //访问这个海坐标queuepiiq;q.push({ x,y });while (q.size()){auto t q.front();q.pop();for (int i 0; i 8; i){int nx t.first dsx[i];int ny t.second dsy[i];if (check(nx, ny) !g[nx][ny] !st_sea[nx][ny]){st_sea[nx][ny] true;q.push({ nx,ny });}if (check(nx, ny) g[nx][ny] !st_road[nx][ny]){ans;bfs_road(nx, ny);}}}
}//bfs算法
//void bfs_road(int x, int y)
//{
// st_road[x][y] true;
// queuepii qr;
// qr.push({ x, y });
// while (qr.size())
// {
// auto t qr.front();
// qr.pop();
// for (int i 0; i 4; i)
// {
// int nx t.firstdrx[i];
// int ny t.seconddry[i];
// if (check(nx, ny) g[nx][ny] !st_road[nx][ny])
// {
// st_road[nx][ny] true;
// qr.push({ nx,ny });
// }
// }
// }
//}//dfs算法
void bfs_road(int x, int y)
{st_road[x][y] true;for (int i 0; i 4; i) //循环为递归的条件{int nx x drx[i];int ny y dry[i];if (check(nx, ny) g[nx][ny] !st_road[nx][ny]) //找到未遍历的递归{st_road[nx][ny] true;bfs_road(nx, ny);}}
}void solve()
{ans 0;cin n m;for (int i 0; i n; i) //初始化被访问的标记{for (int j 0; j m; j){st_sea[i][j] st_road[i][j] false;}}for (int i 0; i n; i) //输入每一行的标记{string s;cin s;for (int j 0; j m; j)g[i][j] s[j] - 0;}bool flag false; //判断特殊情况的印记for (int i 0; i n; i)for (int j 0; j m; j){if (!i || !j ||i n - 1 || j m - 1)if (!g[i][j] !st_sea[i][j]){flag true;bfs_sea(i, j); }}if (!flag) ans1;cout ans endl;
}
signed main()
{ios::sync_with_stdio;cin.tie(0);cout.tie(0);int num 1;while (num--){solve();}
}
