广搜代码
2026-07-22 15:02:24
发布于：广东
28阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
int x, y, step;
bool operator < (const node &b) const{
return b.step < step;
}
};
int n, m, x1, y1, x2, y2;
bool vis[45][45];
char mp[45][45];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
priority_queue <node> q;
bool check(int x, int y){
if(x < 1 || x > n) return 0;
if(y < 1 || y > m) return 0;
if(mp[x][y] == '#') return 0;
if(vis[x][y]) return 0;
return 1;
}
int bfs(int x, int y){
vis[x][y] = 1;
bool flag = 0;
q.push({x, y, 0});
while(!q.empty()){
node head = q.top();
q.pop();
//cout << head.x << ' ' << head.y << ' ' << head.step << endl;
if(head.x == x2 && head.y == y2) return head.step;
for(int i = 0; i < 4; i++){
int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
if(check(xx, yy)){
if(mp[xx][yy] != '.' && mp[xx][yy] != 'W') q.push({xx, yy, head.step + 1 + mp[xx][yy] - '0'});
else q.push({xx, yy, head.step + 1});
vis[xx][yy] = 1;
}
}
}
return -1;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
if(mp[i][j] == 'Z') x1 = i, y1 = j;
if(mp[i][j] == 'W') x2 = i, y2 = j;
}
}//cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
int ans = bfs(x1, y1);
if(ans == -1) cout << "IMPOSSIBLE";
else cout << ans;
return 0;
}
有帮助，赞一个