CP003289.走迷宫3
2023-08-18 21:27:55
发布于：浙江
17阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
struct node {
int x,y,ti;
friend bool operator > (const node a,const node b) {
return a.ti>b.ti;
}
};
int sx,sy,v[5050][5050],g[5050][5050],r,c,ex,ey;
int dx[4]= {-1,0,0,1};
int dy[4]= {0,-1,1,0};
void bfs() {
priority_queue<node,vector<node>,greater<node> > q;
q.push({sx,sy,0});
v[sx][sy]=1;
while(q.size()) {
node head=q.top();
q.pop();
for(int i=0; i<4; i++) {
int tx=head.x+dx[i];
int ty=head.y+dy[i];
int tti=head.ti+1;
if(!v[tx][ty] && g[tx][ty] != '#' && tx >= 1&&tx <= r&&ty >= 1&&ty <= c) {
if(g[tx][ty] >= '1'&&g[tx][ty] <= '9') tti += g[tx][ty] - '0';
q.push({tx,ty,tti});
v[tx][ty] = 1;
if(tx == ex&&ty == ey) {
cout << tti;
return ;
}
}
}
}
cout<<"IMPOSSIBLE";
}
int main() {
cin>>r>>c;
for(int i=1; i<=r; i++) {
for(int j=1; j<=c; j++) {
char c;
cin>>c;
g[i][j]=c;
if(g[i][j]=='Z') {
sx=i;
sy=j;
}
if(g[i][j]=='W') {
ex=i;
ey=j;
}
}
}
bfs();
return 0;
}
有帮助，赞一个