BOJ 1473 - 미로 탈출
BFS인데 현재 회전 상태를 비트마스크로 나타낼 수 있다. 가로 세로 길이가 작으므로 정점은 총 의 가지수가 존재하게 된다.
이는 대략 백만개이므로 최단거리를 구하는 BFS를 수행해줄 수 있다.
에서 방향으로 현재 비트마스크에 따라서 문이 열려있는지 확인하는 코드이다.
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;
};
면 항상 가능, 면 항상 불가능하다.
만약 라면 원래는 세로()로 열려있었는데, 에서 행과 가 문이 돌아간 상태인지를 확인한다.
이 parity가 짝수면 기존 상태와 다르지 않은것이고 홀수면 반대가 된 것이다.
Comments