[17244] 아맞다우산

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

17244번: 아맞다우산

<문제>

"[1194] 달이 차오른다, 가자."와 유사한 문제이다.

현재 가진 물건을 비트로 나타내주어 현재 정점을 표시해줄 수 있는데, 입력으로 들어오는게

전부 'X'로 구분되어 있지 않아서, 이들에 고유의 번호를 할당해주어야 한다.

왼쪽위부터 훑으면서, 1번째로 나온 X는 '1', 2번째로 나온 X는 '2'..처럼 바꿔주어야

몇번째 비트를 켜야할지를 판별할 수 있게된다.

 

사실 '1'부터 '5'까지 채워준건 순수한 취향의 영역. 'A'부터 'E'로 채우든, '0'부터 '4'이든...

중요한건 아스키코드상 연속적이어야 '-'연산자로 간단히 구현이 가능하다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[52][52];
bool visited[52][52][1 << 5];
typedef struct {
    int y, x, turn, key;
} state;
int main(void) {
    cin >> m >> n;
    int i, j, keyNum = 0;
    queue<state> q;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') {
                q.push({i, j, 0, 0});
                visited[i][j][0] = true;
            }
            if (a[i][j] == 'X') a[i][j] = ++keyNum + '0';
        }
    int end = (1 << keyNum) - 1;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (a[cur.y][cur.x] == 'E' && cur.key == end) {
            cout << cur.turn;
            break;
        }
        for (i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == '#' || visited[y][x][cur.key]) continue;
            if (a[y][x] == '.' || a[y][x] == 'S' || a[y][x] == 'E') {
                visited[y][x][cur.key] = true;
                q.push({y, x, cur.turn + 1, cur.key});
            } else if ('1' <= a[y][x] && a[y][x] <= '1' + keyNum) {
                int nKey = cur.key | (1 << (a[y][x] - '1'));
                q.push({y, x, cur.turn + 1, nKey});
                visited[y][x][nKey] = true;
            }
        }
    }
    return 0;
}