質問リンク

https://www.acmicpc.net/problem/1194

質問する

に答える

これはBFS+ビットシールドの問題です.
問題の核心は次のとおりです.

1.ビットマスクを使用してキーがあるかどうかを確認する

鍵を携帯するかどうかはアクセスできるかどうかによって決まるので、ビットマスクで鍵を携帯するかどうかをチェックしました.

ex 1)鍵の取得

現在aキーとdキーを持っていると仮定し、次のアクセス領域にキーfがある場合は、ビット演算(|)でキーを取得できます.
key : fedcba
now : 001001 (9)      f : 100000 (32)
===============
         101001 (41)
すなわち、now=now|fで鍵を得ることができる.

鍵があるかどうか

cキーとdキーを持ち、次のアクセス領域に文Cがあると仮定すると、ビット演算(&)でアクセス可能かどうかを確認できます.
key : fedcba
now : 001100 ( 12 )
    C : 000100 ( 4 )
===============
        000100
つまり、key&C=Cがtrueの場合は、

2.アクセススケジュールでアクセスするかどうかをチェック

アクセス状況だけでなく、どのキーを使用してアクセスする場所もチェックします.△BOJ 206壁を破壊し移動する問を似たようなタイプで解くと役に立ちます.
鍵の種類はa~fの6種類なので6桁使います.
したがって、最大値は2^6−1=63であるため、配列はvisit[51][51][64]と宣言し、アクセスするかどうかを示す.

コード#コード#

#include <iostream>
#include <queue>
using namespace std;
typedef struct pos {
	int x, y, key;
};

int n, m;
int days;
char maps[51][51];
bool vi[51][51][64];
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };
queue<pos> q;

int bfs() {

	while (!q.empty()) {
		int sz = q.size();
		for (int i = 0; i < sz; i++) {
			int x = q.front().x;
			int y = q.front().y;
			int key = q.front().key;
			q.pop();

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;

				if (maps[nx][ny] == '.') {
					if (!vi[nx][ny][key]) {
						vi[nx][ny][key] = true;
						q.push({ nx,ny,key });
					}
				}
				else if ('a' <= maps[nx][ny] && maps[nx][ny] <= 'f') {
					int temp_key = 1;
					temp_key <<= (maps[nx][ny] - 'a');
					int nkey = key | temp_key;
					if (!vi[nx][ny][nkey]) {
						vi[nx][ny][nkey] = true;
						q.push({ nx,ny,nkey });
					}
				}
				else if ('A' <= maps[nx][ny] && maps[nx][ny] <= 'F') {
					int temp_key = 1;
					temp_key <<= (maps[nx][ny] - 'A');
					if ( ( (temp_key & key) == temp_key ) && !vi[nx][ny][key]) {
						vi[nx][ny][key] = true;
						q.push({ nx,ny,key });
					}//열쇠 있는 경우
				}
				else if(maps[nx][ny]=='1'){
					return days+1;
				}

			}//for j
		}//for i 
		days++;
	}//while(!q.empty())
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == '0') {
				vi[i][j][0] = true;
				maps[i][j] = '.';
				q.push({ i,j,0 });
			}
		}
	}
	cout << bfs();
}

ポスト

ビットマスクの概念をよく把握している問題だと思います.
BeatMaskingの問題を解決した経験はありませんが、いい練習でした.