BFS题解，点个赞吧！
2025-11-24 21:42:07
发布于：北京
21阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node{
int x,y,step;
};
void bfs(){
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;
while(q.size()){
node now=q.front();
q.pop();
if(now.x==gx&&now.y==gy){
cout<<now.step;
return ;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<0||nx>n+1||ny<0||ny>m+1) continue;
if(vis[nx][ny]||a[nx][ny]=='#') continue;
vis[nx][ny]=true;
q.push({nx,ny,now.step+1});
}
}
}
int main(){
cin>>n>>m>>sx>>sy>>gx>>gy;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
bfs();
return 0;
}
全部评论 3
#define _CRT_SECURE_NO_WARNINGS // #include "bits/stdc++.h" #include <iostream> #include <queue> using namespace std; const int maxn = 55; char map[maxn][maxn]; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; bool vis[maxn][maxn]; int n, m, sy, sx, gy, gx; class node { public: int x, y, steps; }; bool check(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == '.' && vis[x][y] == 0; } int bfs() { queue<node> q; q.push({ sy,sx,0 }); vis[sy][sx] = 1; while (!q.empty()) { node f = q.front(); q.pop(); if (f.x == gy && f.y == gx) { return f.steps; } for (int i = 0; i < 4; i++) { int nx = f.x + dx[i]; int ny = f.y + dy[i]; int step = f.steps + 1; if (check(nx, ny)) { q.push({ nx,ny,step }); vis[nx][ny] = 1; } } } } int main() { // freopen("input.in", "r", stdin); // freopen("output.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m >> sy >> sx >> gy >> gx; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> map[i][j]; } } cout << bfs() << endl; // fclose(stdin); // fclose(stdout); return 0; }2025-12-28 来自 广东
0
有帮助，赞一个