题目：http://poj.org/problem?id=2157
题意比较简单，就是走迷宫，然后有些地方是需要钥匙才能打开，并且是需要集齐这扇门的所有钥匙才能打开的
思路就是，首先广搜一下，并且将所有可以收集的钥匙都收集起来，看可不可以达到目的地，如果可以，那就不需要再走下去了，如果不可以，这时就把能打开的门全部打开，然后再重复上述步骤，一直到到达目的地，或者还有门打不开并且到不了目的地，结束算法
代码：
#include<cstdio> #include<cstring> #define MAXN 21 #include<queue> using namespace std; char maps[MAXN][MAXN]; int visited[MAXN][MAXN]; int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; int N, M, sx, sy, ex, ey; int key_num[5]; int count[5]; struct Point{ int px, py; }; struct Door{ int x, y; }; Door doors[5]; bool BFS() { Point start; start.px = sx; start.py = sy; memset(visited, 0, sizeof(visited)); queue<Point>Q; Q.push(start); while(!Q.empty()) { Point hd = Q.front(); Q.pop(); if(maps[hd.px][hd.py] == 'G') { return true; } for(int i = 0; i < 4; ++ i) { int x = hd.px + dir[i][0]; int y = hd.py + dir[i][1]; if(x < 0 || x >= M || y < 0 || y >= N) { continue; } if(visited[x][y] || maps[x][y] == 'X' || maps[x][y] >= 'A' && maps[x][y] <= 'E') { continue; } visited[x][y] = 1; if(maps[x][y] >= 'a' && maps[x][y] <= 'e') { count[maps[x][y] - 'a']++; maps[x][y] = '.'; } Point t; t.px = x; t.py = y; Q.push(t); } } return false; } int main() { freopen("poj2157.txt", "r", stdin); while(scanf("%d%d", &M, &N), M, N) { memset(key_num, 0, sizeof(key_num)); memset(count, -1, sizeof(count)); for(int i = 0; i < M; ++ i) { scanf("%s", maps[i]); for(int j = 0; j < N; ++ j) { if(maps[i][j] == 'S') { sx = i; sy = j; } if(maps[i][j] == 'G') { ex = i; ey = j; } if(maps[i][j] >= 'a' && maps[i][j] <= 'e') {//记录每种钥匙的总数，在判断是否可以打开门的时候用 key_num[maps[i][j] - 'a']++ ; } if(maps[i][j] >= 'A' && maps[i][j] <= 'E') {//记录所有门的位置，这里应该是每种门只有一扇的，discuss里面说的不能信 doors[maps[i][j] - 'A'].x = i; doors[maps[i][j] - 'A'].y = j; } } } if(BFS()) {//不需要打开门，就可以直接到达目的地 printf("YES\n"); } else { while(1) { bool door_open = false;//标记是否有门可以被打开 for(int i = 0; i <5; ++ i) { if(count[i] == -1) {//不存在这扇门的钥匙 continue; } else if(count[i] == key_num[i] - 1) {//有这扇门的钥匙，并且找到的钥匙的个数刚好等于所需的钥匙的个数，这里减一是因为初始化时memset是把count置成-1的 count[i] = -1;//可以打开这扇门，所有找到的这扇门的钥匙都被用掉了 maps[doors[i].x][doors[i].y] = '.';//修改地图 door_open = true;//有门可以被打开 } } if(door_open) { if(BFS()) {//打开某些门后可以到达目的地 printf("YES\n"); break; } } else {//没有门可以打开 printf("NO\n"); break; } } } } } |