bfs题解
2023-08-17 14:33:33
发布于:广东
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
char a[25][25];
int v[25][25];
struct node {
int x,y;
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void BFS(int sx,int sy,int n,int m) {
memset(v,0x3f,sizeof(v));
queue<node> que;
que.push({sx,sy});
v[sx][sy]=0;
while (!que.empty()) {
node t=que.front();
que.pop();
for (int i=0;i<4;i++) {
int xx=t.x+dx[i];
int yy=t.y+dy[i];
if (a[xx][yy]!='#'&&xx>=0&&xx<n&&yy>=0&&yy<m) {
if (v[xx][yy]0x3f3f3f3f)que.push({xx,yy});
if (a[xx][yy]>='0'&&a[xx][yy]<='9') {
int k=v[t.x][t.y]+1+(a[xx][yy]-'0');
if (k<v[xx][yy]) {
v[xx][yy]=k;
que.push({xx,yy});
}
}else{
v[xx][yy]=min(v[t.x][t.y]+1,v[xx][yy]);
}
}
}
}
}
int main() {
int n,m;
cin>>n>>m;
int sx,sy,ex,ey;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
cin>>a[i][j];
if (a[i][j]'Z') {
sx=i,sy=j;
}else if (a[i][j]=='W') {
ex=i,ey=j;
}
}
}
BFS(sx,sy,n,m);
if (v[ex][ey]==0x3f3f3f3f) {
printf("IMPOSSIBLE");
}else{
printf("%d",v[ex][ey]);
}
return 0;
}
这里空空如也
有帮助,赞一个