小蓝得到了一副大小为 M × N 的格子地图,可以将其视作一个只包含字符‘0’(代表海水)和 ‘1’(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0, y0),(x1, y1), . . . ,(xk−1, yk−1),其中(x(i+1)%k , y(i+1)%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 pair<int, int>pii; //结果提二维
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 ans=0;
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; //访问这个海坐标
queue<pii>q;
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;
// queue<pii> qr;
// qr.push({ x, y });
// while (qr.size())
// {
// auto t = qr.front();
// qr.pop();
// for (int i = 0; i < 4; i++)
// {
// int nx =t.first+drx[i];
// int ny = t.second+dry[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) ans=1;
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio;
cin.tie(0);
cout.tie(0);
int num = 1;
while (num--)
{
solve();
}
}
原文地址:https://blog.csdn.net/toptopniba/article/details/135918097
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_63837.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!