2206번: 벽 부수고 이동하기

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


$O(nm)$

벽을 부순적이 있는지 유무에 따라 새로운 노드를 만들어 BFS를 이용한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, m, ck[1000][1000][2] = { 1 }, c[1000][1001], r = 1e9;
struct st { int x, y, z; };
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%1d", &c[i][j]);
    queue<st> q;
    q.push({ 0,0,0 });
    while (!q.empty()) {
        st h = q.front();
        q.pop();
        if (h.x == n - 1 && h.y == m - 1) r = min(r, ck[n - 1][m - 1][h.z]);
        for (int i = 0; i < 4; i++) {
            int tx = h.x + fx[i], ty = h.y + fy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m || h.z&&c[tx][ty] || ck[tx][ty][h.z | c[tx][ty]]) continue;
            ck[tx][ty][h.z | c[tx][ty]] = ck[h.x][h.y][h.z] + 1;
            q.push({ tx,ty,h.z | c[tx][ty] });
        }
    }
    printf("%d", r == 1e9 ? -1 : r);
    return 0;
}