[백준 16933] 벽 부수고 이동하기 3, C++

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

16933번: 벽 부수고 이동하기 3

벽 부수고 이동하기 시리즈 문제다. 0은 빈 칸, 1은 벽이다. 이동하는 방법은 상하좌우로 움직일 수 있고, 그 자리에 멈출 수 도 있다. 부술수 있는 벽의 개수가 주어지고, 벽은 낮에만 부술수 있다. 따라서 위치 좌표, 벽을 부순 개수, 낮밤을 저장할 4차원의 배열이 필요하다. 벽 부수고 이동하기 2 문제에서 낮밤만 추가된 문제로 낮밤을 표시하기 위해 3차원 배열을 4차원 배열로 바꾸기만 하면된다. 추가적으로 그 자리에 멈출 수 도 있기 때문에 먼저 상하좌우로 이동하고 멈출 경우를 추가하면 된다.

#include <cstdio>
#include <queue>
#include <tuple>
 
using namespace std;
 
int map[1001][1001];
int d[1001][1001][11][2] = {0}; // 0 낮, 1 밤
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
    int n, m, l;
    scanf("%d %d %d", &n, &m, &l);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
    d[0][0][0][0] = 1;
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(0, 0, 0, 0));
 
    while (!q.empty()) {
 
        // (x, y) 좌표, z 벽을 부순 개수, flag 낮밤
        int x, y, z, flag;
        tie(x, y, z, flag) = q.front();
        q.pop();
        
        // 상하좌우로 이동하기
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            // 범위 확인
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            // 처음 가는 방향이고 빈 칸일 경우
            if (map[nx][ny] == 0 && d[nx][ny][z][1-flag] == 0) {
                d[nx][ny][z][1-flag] = d[x][y][z][flag] + 1;
                q.push(make_tuple(nx, ny, z, 1-flag));
            }
 
            // 낮이고, 벽을 부술수 있을 경우
            if (flag == 0 && z+1 <= l && map[nx][ny] == 1 && d[nx][ny][z+1][1-flag] == 0) {
                d[nx][ny][z+1][1-flag] = d[x][y][z][flag] + 1;
                q.push(make_tuple(nx, ny, z+1, 1-flag));
            }
        }
 
        // 그자리에 멈출 경우
        if (d[x][y][z][1-flag] == 0) {
            d[x][y][z][1-flag] = d[x][y][z][flag] + 1;
            q.push(make_tuple(x,y,z,1-flag));
        }
    }
 
    int ans = -1;
    for (int i = 0; i <= l; i++) {
        for (int j = 0; j < 2; j++) {
            if (d[n-1][m-1][i][j] == 0) continue;
            if (ans == -1 || ans > d[n-1][m-1][i][j]) {
                ans = d[n-1][m-1][i][j];
            }
        }
    }
    printf("%d\n", ans);
}