[蓝桥杯]真题讲解：岛屿个数（BFS遍历图）
一、视频讲解视频讲解
https://i-blog.csdnimg.cn/blog_migrate/aba78cf33c8cbcca520e742e97471f8c.png
二、暴力代码（也是正解代码）
//岛屿个数：搜索（BFS/DFS）
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 100;
int g;//存地图
int n, m;//地图的长和宽
//避免走重复路造成死循环
bool st_sea;//判断哪个海已经访问过了。
bool st_road;//判断哪个陆地已经访问过了。
//方向向量
//海水的方向向量
int dx = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy = {-1, 0, 1, 1, 1, 0, -1, -1};
//陆地的方向向量
int ddx = {-1, 0, 1, 0};
int ddy = {0, 1, 0, -1};
int ans = 0;
//判断你是否超越了地图的边界。
bool check(int x, int y)
{
return ( x >= 0 and x < n and y >= 0 and y < m);
}
//找到了x,y所在的岛屿，并且把该岛屿中的其他的1都标记成了true。
void bfs_road(int x, int y)
{
queue<pii>q;
st_road = true;
q.push({x, y});
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int nx = t.first + ddx;
int ny = t.second + ddy;
if(check(nx, ny) and g and !st_road)
{
st_road = true;
q.push({nx, ny});
}
}
}
}
void bfs_sea(int x, int y)
{
queue<pii>q;
st_sea = true;
q.push({x, y});
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 8; i ++)
{
int nx = t.first + dx;
int ny = t.second + dy;
if(check(nx, ny) and !g and !st_sea)
{
st_sea = true;
q.push({nx, ny});
}
if(check(nx, ny) and g and !st_road)
{
ans ++;
bfs_road(nx, ny);
}
}
}
}
void solve()
{
cin >> n >> m;
ans = 0;
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
st_sea = st_road = false;
for(int i = 0; i < n; i ++)
{
string s; cin >> s;
for(int j = 0; j < m; j ++)
g = s - '0';
}
bool flag = false;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(!i || i == n - 1 || !j || j == m - 1)
{
if(!g && !st_sea)
{
flag = true;
bfs_sea(i, j);
}
}
}
}
if(!flag)
ans = 1;
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--)
solve();
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]