Hdu 1072 【广搜】.cpp-白红宇

Hdu 1072 【广搜】.cpp

阅读量：5224 次

发布时间：2019-06-14

本文共 2900 字，大约阅读时间需要 9 分钟。

题意：

　　给出一个n*m的矩阵，

　　0 表示不可走

　　1 表示可走

　　2 表示起点

　　3 表示终点

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

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

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

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

思路：

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

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

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

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

　　剩下就是正常广搜了..

Tips：

　　404..

Code：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int MAXN = 10; 8 const int INF = 0x1f1f1f1f; 9 10 struct Node11 {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 wall29 1 nothing30 2 start31 3 end32 4 reset33 */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
          
            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 }