迷宫之最少花费时间
2025-01-22 14:49:18
发布于：上海
12阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
char g[20][20];
int n,m,sx,sy,ex,ey;
struct node{
int x,y,d;
};
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int d[20][20];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='Z'){
sx = i;
sy = j;
}
if(g[i][j]=='W'){
ex = i;
ey = j;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[i][j]=0x3f3f3f3f;
}
}
queue<node> q;
q.push({sx,sy,0});
d[sx][sy] = 0;
while(q.size()){
node t = q.front();
q.pop();
for(int i=0;i<4;i++){
int nx = t.x+dir[i][0];
int ny = t.y+dir[i][1];
if(nx<1 || ny<1 || nx>n || ny>m || g[nx][ny]=='#')continue;
int op = (g[t.x][t.y] >='0' && g[t.x][t.y] <='9')?g[t.x][t.y]-'0':0;
if(d[nx][ny] > d[t.x][t.y] + 1 + op){
d[nx][ny] = d[t.x][t.y]+1+op;
q.push({nx,ny,d[nx][ny]});
}
}
}
if(d[ex][ey]==0x3f3f3f3f)cout<<"IMPOSSIBLE";
else cout<<d[ex][ey];
return 0;
}
这里空空如也
有帮助，赞一个