[BAE/<JOON> 문제풀이] 9328. 열쇠

www.acmicpc.net/problem/9328

9328번: 열쇠

시뮬레이션 문제인데 생각보다 까다로웠다. 결국 코너케이스 해결 못해서 테스트 케이스 받아서 까봤다.

 

풀이::

 

열쇠가 알파벳이므로 비스마스크로 2^26이므로 int 범위를 벗어나지 않는다.

 

따라서 방문체크 배열에 열쇠 상태를 저장하며 새로운 열쇠가 있는 경우에만 탐색을 허용한다.

 

칸을 방문했다면 해당 칸에 접근했던 모든 열쇠들을 가지고 지역 탐색을 시작한다.

 

만약 열 수 없는 문에 방문한 경우에도 해당 칸에 열쇠 상태는 저장한다.(* 중요)

 

이미 가지고 있는 열쇠 / 열 수 있는 문 / 문서 를 만난 경우 해당 칸을 0으로 바꾼다. 

 

건물의 가장자리의 모든 칸에서 탐색 시작이 가능하므로, 새로운 열쇠를 찾은 경우 가장자리의 모든 칸에서 새로운 탐색을 시작한다.

 

코너케이스::

열수없는 문을 방문했을 때 열쇠 상태를 복사하지 않고 탐색을 종료했다.

 

저 경우 발생하는 문제는 외곽에 있는 문을 열 때 그 순간에 가지고 있던 열쇠로만 문을 열 수 있게 된다.

 

즉, 안쪽에 열 수 있는 문이 있어도 경우에 따라 그 문을 열지 못하는 경우가 생길 수 있게 된다.

 

/*테케 보고 품*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using namespace std;

struct node {
	int x, y;
	int key = 0;
};

int mvx[5] = { 0, 0, 1, 0, -1 };
int mvy[5] = { 0, 1, 0, -1, 0 };

int ch[101][101];
const int mask = (1 << 26);

int main()
{
	int tc;
	cin >> tc;
	while (tc--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> arr(n + 1, vector<int>(m + 1));		
		for (int i = 1; i <= n; i++) {
			string imsi;
			cin >> imsi;
			for (int j = 1; j <= m; j++) {
				if (imsi[j - 1] == '*') {
					arr[i][j] = 1;
				}
				else if (imsi[j - 1] == '.') {
					arr[i][j] = 0;
				}
				else if (imsi[j - 1] == '$') {
					arr[i][j] = 2;
				}
				else {
					arr[i][j] = imsi[j - 1];
				}
			}
		}			
		string k;
		cin >> k;		
		int currentkey = 0;
		if (k != "0") {
			for (int i = 0; i < k.length(); i++) {
				int kval = k[i] - 97;
				currentkey |= (1 << (kval));
			}			
		}

		queue<node> q;
		int doccnt = 0;

		for (int i = 1; i <= n; i++) {
			if (arr[i][1] >= 97) {
				currentkey |= (1 << (arr[i][1] - 97));
				arr[i][1] = 0;
			}
			if (arr[i][m] >= 97) {
				currentkey |= (1 << (arr[i][m] - 97));
				arr[i][m] = 0;
			}
		}
		for (int i = 1; i <= m; i++) {
			if (arr[1][i] >= 97) {
				currentkey |= (1 << (arr[1][i] - 97));
				arr[1][i] = 0;
			}
			if (arr[n][i] >= 97) {
				currentkey |= (1 << (arr[n][i] - 97));
				arr[n][i] = 0;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				ch[i][j] = mask;
			}
		}

		for (int i = 1; i <= n; i++) {
			ch[i][1] = currentkey;
			if (arr[i][1] == 0 || arr[i][1] == 2 || (arr[i][1] >= 65 && arr[i][1] <= 90 && (currentkey & (1 << (arr[i][1] - 65))))) {
				if (arr[i][1] == 2) {
					doccnt++;
				}
				arr[i][1] = 0;
				q.push({ i, 1, currentkey });
			}			
			ch[i][m] = currentkey;
			if (arr[i][m] == 0 || arr[i][m] == 2 || (arr[i][m] >= 65 && arr[i][m] <= 90 && (currentkey & (1 << (arr[i][m] - 65))))) {
				if (arr[i][m] == 2) {
					doccnt++;
				}
				arr[i][m] = 0;
				q.push({ i, m, currentkey });
			}
		}

		for (int i = 1; i <= m; i++) {
			ch[1][i] = currentkey;
			if (arr[1][i] == 0 || arr[1][i] == 2 || (arr[1][i] >= 65 && arr[1][i] <= 90 && (currentkey & (1 << (arr[1][i] - 65))))) {
				if (arr[1][i] == 2) {
					doccnt++;
				}
				arr[1][i] = 0;
				q.push({ 1, i, currentkey });
			}
			ch[n][i] = currentkey;
			if (arr[n][i] == 0 || arr[n][i] == 2 || (arr[n][i] >= 65 && arr[n][i] <= 90 && (currentkey & (1 << (arr[n][i] - 65))))) {
				if (arr[n][i] == 2) {
					doccnt++;
				}
				arr[n][i] = 0;
				q.push({ n, i, currentkey });
			}
		}


		while (!q.empty()) {
			auto cur = q.front();
			q.pop();
			for (int i = 1; i <= 4; i++) {
				int mx = cur.x + mvx[i];
				int my = cur.y + mvy[i];


				if (mx > n || mx < 1 || my > m || my < 1) continue;

				cur.key |= ch[cur.x][cur.y];

				if(((ch[mx][my] & cur.key) == cur.key && ch[mx][my] != mask) || arr[mx][my] == 1 ||
					(arr[mx][my] >= 65 && arr[mx][my] <= 90 && (cur.key & (1 << (arr[mx][my] - 65))) == 0)) {
					if (ch[mx][my] == mask) {
						ch[mx][my] = cur.key;
					}
					else {
						ch[mx][my] |= cur.key;
					}									
					continue;
				}

				if (ch[mx][my] == mask) {
					ch[mx][my] = cur.key;
				}
				else {
					ch[mx][my] |= cur.key;
				}			

				int key = ch[mx][my];
				currentkey |= key;

				if (arr[mx][my] >= 65 && arr[mx][my] <= 90) {
					arr[mx][my] = 0;
				}

				if (arr[mx][my] == 2) {
					doccnt++;
					arr[mx][my] = 0;
				}

				if (arr[mx][my] >= 97) {					
					if ((cur.key & (1 << (arr[mx][my] - 97))) == 0) {
						key |= (1 << (arr[mx][my] - 97));
						for (int j = 1; j <= n; j++) {
							if (ch[j][1] == mask) {
								ch[j][1] = key;
							}
							else {
								ch[j][1] |= key;
							}
							if (arr[j][1] == 0 || (arr[j][1] >= 65 && arr[j][1] <= 90 && (key & (1 << (arr[j][1] - 65))))) {							
								arr[j][1] = 0;
								q.push({ j, 1, key });
							}
							if (ch[j][m] == mask) {
								ch[j][m] = key;
							}
							else {
								ch[j][m] |= key;
							}
							if (arr[j][m] == 0 || (arr[j][m] >= 65 && arr[j][m] <= 90 && (key & (1 << (arr[j][m] - 65))))) {
								arr[j][m] = 0;
								q.push({ j, m, key });
							}
						}

						for (int j = 1; j <= m; j++) {
							if (ch[1][j] == mask) {
								ch[1][j] = key;
							}
							else {
								ch[1][j] |= key;
							}
							if (arr[1][j] == 0 || (arr[1][j] >= 65 && arr[1][j] <= 90 && (key & (1 << (arr[1][j] - 65))))) {
								arr[1][j] = 0;
								q.push({ 1, j, key });
							}
							if (ch[n][j] == mask) {
								ch[n][j] = key;
							}
							else {
								ch[n][j] |= key;
							}
							if (arr[n][j] == 0 || (arr[n][j] >= 65 && arr[n][j] <= 90 && (key & (1 << (arr[n][j] - 65))))) {
								arr[n][j] = 0;
								q.push({ n, j, key });
							}
						}
					}
					arr[mx][my] = 0;
				}

				q.push({ mx, my, key });
			}
		}

		/*for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (arr[i][j] == 1) {
					cout << "*";
				}
				else if (arr[i][j] == 2) {
					cout << "$";
				}
				else if (arr[i][j] == 0) {
					cout << ".";
				}
				else {
					cout << (char)arr[i][j];
				}
			}
			cout << "\n";
		} */
		cout << doccnt << "\n";
	}
	
	return 0;
}