HDU 1072 (不一样的入队条件) Nightmare

浏览数：27 / 时间：2015年06月09日

之前的BFS都是需要一个标记数组，但这个题不一样，因为可能一个格子不止走一次。

那么我们就要寻找新的入队条件：left比上次经过的时候大才入队(left表示上次经过该点时剩余的时间)。

为什么呢？我们重复走过一个点只有一个可能，那就是为了去取那个，所以如果取完后再回头经过这个点的时候剩余时间变多了，我们的目的就达到了。

left数组初值为0

优化：

重置时间的装置最多取一次就够了，所以可以再开一个标记数组vis记录装置是否用过。

 1 //#define LOCAL
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std; 
 6 
 7 struct Point
 8 {
 9     int x, y;
10     int steps;
11     int time;
12 }start, end;
13 
14 int map[10][10], vis[10][10], left[10][10];
15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16 int row, col;
17 
18 void BFS(void)
19 {
20     queue<Point> qu;
21     start.time = 6, start.steps = 0;
22     qu.push(start);
23     while(!qu.empty())
24     {
25         Point fir = qu.front();
26         qu.pop();
27         if(fir.time == 0)    continue;
28         if(fir.x == end.x && fir.y == end.y)
29         {
30             printf("%d\n", fir.steps);
31             return;
32         }
33         if(map[fir.x][fir.y] == 4)
34             fir.time = 6;
35         for(int i = 0; i < 4; ++i)
36         {
37             int xx = fir.x + dir[i][0];
38             int yy = fir.y + dir[i][1];
39             if(xx<0 | xx>=row | yy<0 | yy>=col | (!map[xx][yy]))
40                 continue;
41             Point next;
42             next.x = xx, next.y = yy;
43             next.time = fir.time - 1;
44             next.steps = fir.steps + 1;
45             if(map[xx][yy] == 4 && vis[xx][yy])
46                 continue;
47             if(next.time > left[xx][yy])
48             {
49                 left[xx][yy] = next.time;
50                 qu.push(next);
51             }
52         }
53     }
54     printf("-1\n");
55 }
56 
57 int main(void)
58 {
59     #ifdef LOCAL
60         freopen("1072in.txt", "r", stdin);
61     #endif
62 
63     int T;
64     scanf("%d", &T);
65     while(T--)
66     {
67         scanf("%d%d", &row, &col);
68         for(int i = 0; i < row; ++i)
69             for(int j = 0; j < col; ++j)
70             {
71                 scanf("%d", &map[i][j]);
72                 if(map[i][j] == 2)
73                     start.x = i, start.y = j;
74                 if(map[i][j] == 3)
75                     end.x = i, end.y = j;
76             }
77         memset(vis, 0, sizeof(vis));
78         memset(left, 0, sizeof(left));
79         BFS();
80     }
81     return 0;
82 }