AKSZ - 广度优先搜索
2024-06-16 14:44:43
发布于:广东
1.迷宫类问题(示例代码)
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
int n,m,sx,sy,ex,ey,step[1001][1001];
char a[1001][1001];
struct node
{
int x,y;
};
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void bfs()
{
memset(step,-1,sizeof(step));
queue<node> q;
q.push(node{sx,sy});
step[sx][sy] = 0;
while(!q.empty())
{
node tmp = q.front();
q.pop();
for(int i = 1;i <= 4;i++)
{
int tx = tmp.x + dir[i - 1][0];
int ty = tmp.y + dir[i - 1][1];
if(in(tx,ty) && a[tx][ty] != '#' && step[tx][ty] == -1)
{
q.push(node{tx,ty});
step[tx][ty] = step[tmp.x][tmp.y] + 1;
}
}
}
}
int main()
{
cin >> n >> m >> sx >> sy >> ex >> ey;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> a[i][j];
}
}
bfs();
cout << step[ex][ey] << endl;
return 0;
}
2.连通块问题(示例代码)
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
int n,m,ans = 0;
char a[1001][1001];
struct node
{
int x,y;
};
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void bfs(int sx,int sy)
{
queue<node> q;
q.push(node{sx,sy});
a[sx][sy] = '.';
ans++;
while(!q.empty())
{
node tmp = q.front();
q.pop();
for(int i = 1;i <= 4;i++)
{
int tx = tmp.x + dir[i - 1][0];
int ty = tmp.y + dir[i - 1][1];
if(in(tx,ty) && a[tx][ty] == '*')
{
q.push(node{tx,ty});
a[tx][ty] = '.';
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> a[i][j];
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(a[i][j] == '*')
{
bfs(i,j);
}
}
}
cout << ans << endl;
return 0;
}
这里空空如也
有帮助,赞一个