Hdu 1072 【广搜】.cpp

题意：

　　给出一个n*m的矩阵，

　　0 表示不可走

　　1 表示可走

　　2 表示起点

　　3 表示终点

　　4 表示可走且走到这一步可以满血

　　某人一开始有6滴血，走一步少一滴..到0就死了..

　　可以走到4的位置满血再走..

　　求出最少走几步可以从起点到终点..

思路：

　　广搜，用一个cnt表示现在走了几步，一个cur表示现在的血量..

　　普通的广搜过程中如果已经走过就不可以再走了..但是第三个样例可以看出走过还可以再走..

　　因为普通广搜走过不能再走只是代表这个状态已经访问过了..不需要再次访问，防止死循环..

　　但是现在再次访问的时候因为血量已经不一样了.所以可以再走..

　　剩下就是正常广搜了..

Tips：

　　404..

Code：

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 10;
 8 const int INF = 0x1f1f1f1f;
 9 
10 struct Node
11 {
12     int x;
13     int y;
14     int cnt;
15     int cur;
16 };
17 
18 int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
19 int iCase, n, m;
20 int G[MAXN][MAXN], vis[MAXN][MAXN], dis[MAXN][MAXN];
21 
22 bool check(Node node)
23 {
24     return node.x >= 0 && node.x < n && node.y >= 0 && node.y < m && (!vis[node.x][node.y] || dis[node.x][node.y] < node.cur) && node.cur != 0;
25 }
26 
27 /*
28 0 wall
29 1 nothing
30 2 start
31 3 end
32 4 reset
33 */
34 
35 int main()
36 {
37    // freopen("in.txt", "r", stdin);
38     bool flag;
39     Node ed, node, node1;
40     int ans;
41     scanf("%d", &iCase);
42     while (iCase--) {
43         memset(vis, false, sizeof(vis));
44         memset(dis, INF, sizeof(dis));
45         flag = false;
46         queue<Node> Q;
47         scanf("%d %d", &n, &m);
48         for (int i = 0; i < n; ++i)
49             for (int j = 0; j < m; ++j) {
50                 scanf("%d", &G[i][j]);
51                 if (G[i][j] == 2) {
52                     node.x = i, node.y = j;
53                     node.cnt = 0;
54                     node.cur = 6;
55                     Q.push(node);
56                     dis[i][j] = node.cur;
57                     vis[i][j] = true;
58                 } else if (G[i][j] == 3)
59                     ed.x = i, ed.y = j;
60                 else if (G[i][j] == 0)
61                     vis[i][j] = true;
62         }
63         while (!Q.empty()) {
64             node  = Q.front();
65             if (node.x == ed.x && node.y == ed.y) {
66                 ans = node.cnt;
67                 flag = true;
68                 break;
69             }
70             Q.pop();
71             for (int i = 0; i < 4; ++i) {
72                 node1.x = node.x+dir[i][0];
73                 node1.y = node.y+dir[i][1];
74                 node1.cnt = node.cnt+1;
75                 node1.cur = node.cur-1;
76                 if (check(node1)) {
77                     if (G[node1.x][node1.y] == 4) node1.cur = 6;
78                     dis[node1.x][node1.y] = node.cur;
79                     Q.push(node1);
80                     vis[node1.x][node1.y] = true;
81                 }
82             }
83         }
84         if (flag) printf("%d\n", ans);
85         else puts("-1");
86     }
87     return 0;
88 }

View Code

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1072