首页 > 代码库 > hdu 1885 Key Task (三维bfs)

hdu 1885 Key Task (三维bfs)

2024-07-02 09:57:39   227人阅读

题目

之前比赛的一个题， 当时是崔老师做的，今天我自己做了一下。。。。

 

还要注意用bfs的时候  有时候并不是最先到达的就是答案，比如HDU 3442 这道题是要求最小的消耗血量伤害，但是并不是最先到达目标点的路径

就是最小的伤害，因为每一个点的伤害是 不一样的， 这种情况要用优先队列优化， 对伤害优化。

 

题意：*开始， X出口， b, y, r, g 代表钥匙，分别可以开B, Y，　R, G颜色的门， 钥匙可以多次使用。问最短的步骤。

思路：vis[][]【】数组开三维，第三维记录状态 是否拿到该颜色的钥匙， 如果以相同的状态走到 相同的地方 就是重复，不能加进队列。

第三维用 二进制下相应的位来表示 是否拿到相应的钥匙。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <cmath>
  6 #include <algorithm>
  7 using namespace std;
  8 const int maxn = 100+10;
  9 int vis[maxn][maxn][20], r, c;
 10 char G[maxn][maxn];
 11 int dx[5] = {0,0,1,-1};
 12 int dy[5] = {1,-1,0,0};
 13 char k[5] = {‘b‘, ‘y‘, ‘r‘, ‘g‘};
 14 char d[5] = {‘B‘, ‘Y‘, ‘R‘, ‘G‘};
 15 struct node
 16 {
 17     int x, y, key, step;
 18 } next, pos;
 19 
 20 void bfs(int a, int b)
 21 {
 22     int i, j;
 23     queue<node>q;
 24     memset(vis, 0, sizeof(vis));
 25     next.x = a;
 26     next.y = b;
 27     next.key = 0;
 28     next.step = 0;
 29     q.push(next);
 30     vis[a][b][next.key] = 1;
 31     while(!q.empty())
 32     {
 33         pos = q.front();
 34         q.pop();
 35         for(i = 0; i < 4; i++)
 36         {
 37             next.x = pos.x+dx[i];
 38             next.y = pos.y+dy[i];
 39             next.step = pos.step+1;
 40             if(!(next.x>=1&&next.x<=r&&next.y>=1&&next.y<=c))
 41                 continue;
 42             if(G[pos.x][pos.y]==‘X‘)
 43             {
 44                 printf("Escape possible in %d steps.\n", pos.step);
 45                 return;
 46             }
 47             if(G[next.x][next.y]==‘#‘)
 48                 continue;
 49             if(G[next.x][next.y]>=‘a‘ && G[next.x][next.y]<=‘z‘)
 50             {
 51                 for(j = 0; j < 4; j++)
 52                     if(G[next.x][next.y]==k[j])
 53                         next.key = (pos.key|(1<<j));
 54             }
 55             if(G[next.x][next.y]==‘.‘||G[next.x][next.y]==‘*‘)
 56             {
 57                 next.key = pos.key;
 58             }
 59             if(G[next.x][next.y]>=‘A‘ && G[next.x][next.y]<=‘Z‘)
 60             {
 61                 for(j = 0; j < 4; j++)
 62                     if(G[next.x][next.y]==d[j])
 63                     {
 64                         if(pos.key&(1<<j))
 65                             next.key = pos.key;
 66                         else
 67                             break;
 68                     }
 69                 if(j<4)
 70                     continue;
 71             }
 72             if(vis[next.x][next.y][next.key]==0)
 73             {
 74                 vis[next.x][next.y][next.key] = 1;
 75                 q.push(next);
 76             }
 77         }
 78     }
 79     printf("The poor student is trapped!\n");
 80 }
 81 int main()
 82 {
 83     int i, j;
 84     int a, b;
 85     while(cin>>r>>c)
 86     {
 87         if(r==0 && c==0)  break;
 88         for(i = 1; i <= r; i++)
 89         {
 90             getchar();
 91             for(j = 1; j <= c; j++)
 92             {
 93                 cin>>G[i][j];
 94                 if(G[i][j]==‘*‘)
 95                 {
 96                     a = i;
 97                     b = j;
 98                 }
 99             }
100         }
101         bfs(a, b);
102     }
103     return 0;
104 }

 


联系
我们