AKSZ-BFS
2024-05-19 17:37:21
发布于:广东
模板
#include<bits/stdc++.h>
using namespace std;
struct node{
int x, y; // 当前访问点
int step; // 当前步数
};
const int MAXN = 49;
int n, m;
char mp[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int minStep[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool in(int x, int y){
return (x < 0) || (y < 0) || (x >= n) || (y >= m) || (mp[x][y] == '#');
}
int bfs(int x, int y, int to_x, int to_y){
queue<node> q;
q.push({x, y, 0}); // 将起点状态入队
while(!q.empty())
{
node temp = q.front(); // 取开始点
q.pop();
vis[temp.x][temp.y] = 1;
if(temp.x == to_x && temp.y == to_y)
{
return temp.step;
}
//cout << temp.x << " " << temp.y << endl;
for(int i = 0; i < 4; i++)
{
int go_x = temp.x + dx[i];
int go_y = temp.y + dy[i];
if(in(go_x, go_y) || vis[go_x][go_y])
{
continue;
}
vis[go_x][go_y] = 1;
q.push({go_x, go_y, temp.step + 1});
}
}
return -1;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> mp[i][j];
}
}
cout << bfs(0, 0, n-1, m-1);
return 0;
}
这里空空如也
有帮助,赞一个