走迷宫3
2023-08-07 17:06:04
发布于:浙江
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,ti;
friend bool operator > (node a,node b){
return a.ti > b.ti;
}
};
char g[30][30];
int v[30][30];
int r,c,sx,sy,ex,ey;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void bfs(){
priority_queue<node,vector<node>,greater<node> > q;
q.push({sx,sy,0});
v[sx][sy] = 1;
while(!q.empty()){
node head = q.top();
q.pop();
for(int i = 0;i < 4;i++){
int tx = head.x + dx[i],ty = head.y + dy[i],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++){
cin >> g[i][j];
if(g[i][j] == 'Z') sx = i,sy = j;
if(g[i][j] == 'W') ex = i,ey = j;
}
}
bfs();
return 0;
}
这里空空如也
有帮助,赞一个