本文主要是介绍hdu 1429胜利大逃亡(续) / sdut 2193 救基友记3(BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1429
做了热身赛http://blog.csdn.net/u013081425/article/details/21740001 之后发现这道题好水，之前怎么没刷到呢。。
同样标记数组增加一维，标记到某一点时他拥有钥匙的状态，因为有10种钥匙，所以mark[][][1<<10+10]来标记每到一点的状态。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
struct node
{int x,y;int step;int sta;
}p[410];queue <struct node> que;
char map[30][30];
int n,m,t;
int sx,sy;
int mark[30][30][1<<10+10];void bfs()
{memset(mark,0,sizeof(mark));while(!que.empty()) que.pop();que.push((struct node) {sx,sy,0,0});mark[sx][sy][0] = 1;while(!que.empty()){struct node u = que.front();que.pop();if(u.step >= t){printf("-1\n");return;}if(map[u.x][u.y] == '^'){printf("%d\n",u.step);return;}for(int d = 0; d <= 3; d++){int x = u.x+dir[d][0];int y = u.y+dir[d][1];if(x < 1 || x > n || y < 1 || y > m)continue;int sta = u.sta;int add;if(map[x][y] == '.' || map[x][y] == '@' || map[x][y] == '^'){if(!mark[x][y][sta]){que.push((struct node){x,y,u.step+1,sta});mark[x][y][sta] = 1;}}else if(map[x][y] >= 'a' && map[x][y] <= 'j'){add = map[x][y]-'a';if((sta & (1<<add)) == 0)//注意先判断是否已有这种钥匙，没有再加sta += (1 << add);if(!mark[x][y][sta]){que.push( (struct node) {x,y,u.step+1,sta});mark[x][y][sta] = 1;}}else if(map[x][y] >= 'A' && map[x][y] <= 'J'){add = map[x][y] - 'A';if( (sta & (1<<add)) && !mark[x][y][sta]){que.push((struct node) {x,y,u.step+1,sta});mark[x][y][sta] = 1;}}}}printf("-1\n");
}int main()
{while(~scanf("%d %d %d",&n,&m,&t)){for(int i = 1; i <= n; i++){scanf("%s",map[i]+1);for(int j = 1; j <= m; j++){if(map[i][j] == '@'){sx = i;sy = j;}}}bfs();}return 0;
}
这篇关于hdu 1429胜利大逃亡(续) / sdut 2193 救基友记3(BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
