hdu 1072 Nightmare (bfs+优先队列)

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 struct node{
 8     int x,y;
 9     int time;
10     int sss;
11     friend bool operator < (node a,node b){
12         return a.time > b.time;
13     }
14 };
15 
16 int n,m,sx,sy,ex,ey;
17 int dir[8][2]={1,0,-1,0,0,-1,0,1};
18 int map[10][10];
19 
20 bool inMap(int x,int y){
21     return x>=0&&x<n&&y>=0&&y<m;
22 }
23 
24 int bfs(){
25     node cur,next;
26     priority_queue<node> q;
27     cur.x = sx;
28     cur.y = sy;
29     cur.time = 0;
30     cur.sss = 6;
31     q.push(cur);
32     while(!q.empty()){
33         cur = q.top();
34         q.pop();
35         if(cur.sss<=0)
36             return -1;
37         if(cur.sss>0 && cur.x == ex && cur.y == ey)
38             return cur.time;
39         for(int i=0;i<4;i++){
40             int xx = cur.x + dir[i][0];
41             int yy = cur.y + dir[i][1];
42             if(inMap(xx,yy) && map[xx][yy]!=0 && cur.sss>1){
43                 next.sss = cur.sss-1;
44                 if(map[xx][yy]==4 && next.sss > 0){
45                     next.sss = 6;
46                     map[xx][yy] = 0;
47                 }
48                 next.x = xx;
49                 next.y = yy;
50                 next.time = cur.time + 1;
51                 q.push(next);
52             }
53         }
54     }
55     return -1;
56 }
57 
58 int main(){
59     int t,i,j;
60     cin>>t;
61     while(t--){
62         cin>>n>>m;
63         for(i=0;i<n;i++)
64             for(j=0;j<m;j++){
65                 scanf("%d",&map[i][j]);
66                 if(map[i][j]==2)
67                     sx=i,sy=j;
68                 else if(map[i][j]==3){
69                     ex=i,ey=j;
70                     map[i][j] = 1;
71                 }
72             }
73         cout<<bfs()<<endl;
74     }
75     return 0;
76 }