[C++知识库]POJ 1159:Maze

“ Ctrl AC！一起 AC！”

题目：忘题戳这

分析：可以用bfs，就是将可以走的路存入队列，遇到了门的话把它标记下，先不要开。先把所有能走到路走完，再去看能不能开门，能开门的话，把开门后扩展出的新路存入队列。继续重复该步骤，直到找到终点。队列全空了也找不到，说明无法达到终点。

AC代码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int dx[] = { 0,1,-1,0 };
int dy[] = { 1,0,0,-1 };
struct node {
	int x, y;//深搜坐标
};
int doorkeynow[35];//现存钥匙
int doorkeysum[35];//总钥匙
char map[35][35];
int jiesuo[35][35];//走过的路
int reachdoor[35];//碰到的门
int r1, c1, r2, c2, r, c;//起点，终点，地图大小
void bfs() {
	queue<node> q;
	q.push(node{ r1,c1 });
	int flag = 1;
	while (flag) {
		flag = 0;
		while (!q.empty()) {
			node temp = q.front(); q.pop();
			int nowr = temp.x; int nowc = temp.y;
			if (nowr == r2 && nowc == c2) {
				cout << "YES" << endl;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int rr = nowr + dx[i];
				int cc = nowc + dy[i];
				if (rr <= 0 || rr > r || cc <= 0 || cc > c || map[rr][cc] == 'X') continue;
				if (jiesuo[rr][cc])continue;//如果走过
				if (map[rr][cc] >= 'A' && map[rr][cc] <= 'E') {
					reachdoor[map[rr][cc] - 'A'] = 1;//找到的门
					continue;
				}
				if (map[rr][cc] >= 'a' && map[rr][cc] <= 'e') {
					doorkeynow[map[rr][cc] - 'a']++;//找到了钥匙
				}
				jiesuo[rr][cc] = 1;
				q.push(node{ rr,cc });
			}
		}
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (map[i][j] >= 'A' && map[i][j] <= 'E' && !jiesuo[i][j]) {//没开过的门
					int ch = map[i][j] - 'A';
					if (reachdoor[ch] && doorkeynow[ch] == doorkeysum[ch]) {//把它打开，再走过它
						jiesuo[i][j] = 1;
						q.push(node{ i,j });
						flag = 1;
					}
				}
			}
		}
	}
	cout << "NO" << endl;
	return;
}
int main() {
	while (cin >> r >> c && r && c) {
		memset(reachdoor, 0, sizeof(reachdoor));
		memset(jiesuo, 0, sizeof(jiesuo));
		memset(doorkeynow, 0, sizeof(doorkeynow));
		memset(doorkeysum, 0, sizeof(doorkeysum));
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				cin >> map[i][j];
				if (map[i][j] == 'S') {
					r1 = i, c1 = j;
				}
				if (map[i][j] == 'G') r2 = i, c2 = j;
				if (map[i][j] >= 'a' && map[i][j] <= 'e') doorkeysum[map[i][j] - 'a']++;	
			}
		}
		bfs();
	}
	return 0;
}

感谢阅读！！！

“ Ctrl AC！一起 AC！”