[BOJ-1194]달이차오른다가자

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

[접근방법]

열쇠에 대한 접근을 어떤 방식으로 해야하는지 생각했던 문제

열쇠는 비트 연산을 통하여 저장을 할 수 있다. 

열쇠를 가지고 있을 때 이동 횟수에 대한 표시는 vis[key][row][col] 에 할 수 있다. 

열쇠를 획득하였을 때 현재 key 변수와 있는 키에 대한 값을 시프트연산을 한 후, OR | 을 하여 구한다.

[C++11 source Code BFS]

#include<cstdio>
#include<queue>
using namespace std;
const int M = 55;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
const int INF = 1 << 20;
int ROW, COL;
char imap[M][M];
int vis[64][M][M];
// 1 2 4 8 16 32 <= 63
struct pos {
       int r;
       int c;
       int key;
       int mov;
       pos(int ir, int ic, int ik, int im) :
              r(ir), c(ic), key(ik), mov(im) {}
       pos():r(0),c(0),key(0),mov(0){}
};
void init() {
       for (int t = 0; t < 64; t++) {
              for (int r = 0; r < M; r++) {
                     for (int c = 0; c < M; c++) vis[t][r][c] = INF;
              }
       }
}
int main() {
       scanf("%d%d", &ROW, &COL);
       pos    start;
       for (int r = 0; r < ROW; r++) {
              scanf("%s", imap[r]);
              for (int c = 0; c < COL; c++) {
                     if (imap[r][c] == '0') {
                           start.r = r;
                           start.c = c;
                     }
              }             
       } // input
       init();
       queue<pos> Q;
       Q.push(start);
       int ans = INF;
       while (!Q.empty()) {
              pos here = Q.front(); Q.pop();
              int hr = here.r;
              int hc = here.c;
              int hk = here.key;
              int hm = here.mov;
              if (vis[hk][hr][hc] > hm) vis[hk][hr][hc] = hm;
              else continue;
              for (int i = 0; i < 4; i++) {
                     int tr = hr + dr[i];
                     int tc = hc + dc[i];
                     if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue; // range over
                     
                     if (imap[tr][tc] == '1') {
                           ans = (ans > here.mov + 1) ? here.mov + 1 : ans;
                           continue;
                     }
                     else if ('a' <= imap[tr][tc] && imap[tr][tc] <= 'f') {
                           int there_key = imap[tr][tc] - 'a';
                           there_key = 1 << there_key;
                           Q.push( pos(tr, tc, hk | there_key , hm+1) );
                     }
                     else if ('A' <= imap[tr][tc] && imap[tr][tc] <= 'F') {
                           int there_door = imap[tr][tc] - 'A';
                           there_door = 1 << there_door;
                           int is_open = there_door & hk;
                           if (is_open == there_door) {
                                  Q.push(pos(tr, tc, hk, hm + 1));
                           }
                     }
                     else if (imap[tr][tc] != '#'){
                           Q.push(pos(tr, tc, hk, hm + 1));
                     }
              }
       }
       if (ans == INF) puts("-1");
       else printf("%d", ans);
       return 0;
}