hdu--1072--特别的bfs

这题真的狠特别...因为路径可以走回头路但有一点需要注意

那个重置为0的地方只能走一次因为你这样想当你经过它一次将剩余时间重置之后再走一次它继续重置那你刚刚的路不是白走了吗？

那肯定就不是最优解了所以我们的vis只标记重置点就OK了

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int n , m , endx , endy;
 7 int maze[10][10];
 8 bool vis[10][10];
 9 int dir[4][2]={1,0,-1,0,0,1,0,-1};
10 struct data
11 {
12     int x , y;
13     int step , t;
14 }st;
15 
16 int bfs( )
17 {
18     data now , next;
19     int xx , yy;
20     queue<data>q;
21     while( !q.empty() )
22     {
23         q.pop();
24     }
25     q.push(st);
26     while( !q.empty() )
27     {
28         now = q.front();
29         q.pop();
30         if( now.x == endx && now.y == endy && now.t<=5 )
31         {
32             return now.step;
33         }
34         if( now.t==5 )
35         {
36             continue;
37         }
38         for( int i = 0 ; i<4 ; i++ )
39         {
40             xx = now.x + dir[i][0];
41             yy = now.y + dir[i][1];
42             if( xx>=0 && xx<n && yy>=0 && yy<m && maze[xx][yy]!=0 )
43             {
44                 next.x = xx;
45                 next.y = yy;
46                 next.step = now.step + 1;
47                 if( maze[xx][yy] == 4 && !vis[xx][yy] )
48                 {    
49                     next.t = 0;
50                     vis[xx][yy] = true;    
51                 }
52                 else 
53                 {
54                     next.t = now.t + 1;
55                 }
56                 q.push(next);
57             }
58         }
59     }
60     return -1;
61 }
62 
63 int main()
64 {
65     int t;
66     while( cin >> t )
67     {
68         while( t-- )
69         {
70             cin >> n >> m;
71             memset( vis , false , sizeof(vis) );
72             for( int i = 0 ; i<n ; i++ )
73             {
74                 for( int j = 0 ; j<m ; j++ )
75                 {
76                     cin >> maze[i][j];
77                     if( maze[i][j] == 2 )
78                     {
79                         st.x = i;
80                         st.y = j;
81                         st.step = st.t = 0;
82                     }
83                     else if( maze[i][j] == 3 )
84                     {
85                         endx = i;
86                         endy = j;
87                     }
88                 }
89             }
90             cout << bfs() << endl;
91         }
92     }
93     return 0;
94 }

View Code

today:

　　听到有人说 20多岁是不是人生中最艰难的一段时间？

　　似乎是

　　似乎不是

　　谁知道呢

just follow your heart