广搜——路径寻找

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<queue>
 8 using namespace std;
 9 struct node{
10     int x;
11     int y;
12     int dist;
13     friend bool operator < (node a,node b){
14         return a.dist > b.dist;
15     }
16 };
17 priority_queue<node> q;
18 int t,x,y,startx,starty,endx,endy,map[50][50],jud[50][50];
19 int dx[4] = {-1,0,1,0};
20 int dy[4] = {0,-1,0,1};
21 void input(){
22     cin>>t>>x>>y;
23     char cmd;
24     for(int i = 1;i <= y;i++){
25         for(int j = 1;j <= x;j++){
26             cin>>cmd;
27             if(cmd == ‘.‘) map[i][j] = 1;
28             if(cmd == ‘#‘) map[i][j] = 2;
29             if(cmd == ‘o‘) map[i][j] = 3;
30             if(cmd == ‘s‘){
31                 map[i][j] = 1;
32                 startx = j;
33                 starty = i;
34             }
35             if(cmd == ‘m‘){
36                 map[i][j] = 1;
37                 endx = j;
38                 endy = i;
39             }
40         }
41     }
42     node tmp;
43     tmp.x = startx;
44     tmp.y = starty;
45     tmp.dist = 0;
46     q.push(tmp);
47     for(int i = 1;i <= 40;i++){
48         for(int j = 1;j <= 40;j++){
49             jud[i][j] = 100000000;
50         }
51     }
52 }
53 bool bfs(){
54     node now,next;
55     int nx,ny;
56     while(!q.empty()){
57         now = q.top();
58         q.pop();
59         for(int i = 0;i < 4;i++){
60             nx = now.x + dx[i];
61             ny = now.y + dy[i];
62             if(nx < 1 || nx > x || ny < 1 || ny > y || map[ny][nx] == 3 ||jud[ny][nx] <= now.dist + map[ny][nx]) continue;
63             next.x = nx;
64             next.y = ny;
65             next.dist = now.dist + map[ny][nx];
66             if(nx == endx && ny == endy){
67                 if(next.dist >= t) return false;
68                 else{
69                     cout<<next.dist<<endl;
70                     return true;
71                 }
72             }
73             q.push(next);
74             jud[ny][nx] = next.dist;
75         }
76     }
77 }
78 int main(){
79     input();
80     if(!bfs()) cout<<55555<<endl;
81     return 0;
82 }