BOJ 1473 - 미로 탈출

BOJ 1473 - 미로 탈출

BFS인데 현재 회전 상태를 비트마스크로 나타낼 수 있다. 가로 세로 길이가 작으므로 정점은 총 $W \cdot H \cdot 2^W \cdot 2^H$ 의 가지수가 존재하게 된다.

이는 대략 백만개이므로 최단거리를 구하는 BFS를 수행해줄 수 있다.

$(y,x)$ 에서 $d$ 방향으로 현재 비트마스크에 따라서 문이 열려있는지 확인하는 코드이다.

function<bool(int, int, int, int, int)>
      passable = [&](int y, int x, int dir, int ybit, int xbit) -> bool {
      if (b[y][x] == 'A') return 1;
      if (b[y][x] == 'B') return 0;

      int vert = b[y][x] == 'C';
      int hor = b[y][x] == 'D';

      int parity = !!(ybit & (1 << y)) + !!(xbit & (1 << x));
      parity %= 2;

      if (parity) vert ^= 1, hor ^= 1;
      if (dir == 0 || dir == 2) return vert;
      else return hor;
   };

$A$면 항상 가능, $B$면 항상 불가능하다.

만약 $C$ 라면 원래는 세로($d=0,\,2$)로 열려있었는데, $(y,x)$ 에서 $y$ 행과 $x$ 가 문이 $90 \degree$돌아간 상태인지를 확인한다.

이 parity가 짝수면 기존 상태와 다르지 않은것이고 홀수면 반대가 된 것이다.