[백준] 벽 부수고 이동하기 3(c++)

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

벽 부수고 이동하기 2와 비슷하지만

낮과 밤이 바뀌는 조건과 여러 방향으로 벽을 만났을 때 중복으로 해당 좌표의 거리(시간)가 올라가지 않게 하는 것이 포인트였다.

또한 벽을 부수는 것이 값을 오염시킬 수 있어서 나눠서 반복문을 진행시켜주었다.

 

---

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <climits>
#include <queue>
#include <set>
#include <math.h>
#include <stack>
#include <deque>

using namespace std;

struct wall {
    int destroy, is_night, y, x;
};

char arr[1001][1001] = { 0 };
int visited[11][1001][1001] = { 0 };

int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0, 1, -1 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, k, ans = 1000001;
    queue<wall> q;

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;

        for (int j = 0; j < m; j++) {
            arr[i][j] = temp[j];
        }
    }

    q.push({ 0,0,0,0 });
    visited[0][0][0] = 1;

    while (!q.empty()) {
        wall cur = q.front();

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            int destroy = cur.destroy;
            int is_night = cur.is_night;

            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

            // arr[ny][nx] == 0 && !visited[destroy][ny][nx]는 가능한 경우
            if ((arr[ny][nx] == '0') && !visited[destroy][ny][nx]) {
                visited[destroy][ny][nx] = visited[destroy][cur.y][cur.x] + 1;
                q.push({ destroy, !is_night, ny,nx });
            }
        }

        bool flag = false;

        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            int destroy = cur.destroy;
            int is_night = cur.is_night;
           

            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

            if ((arr[ny][nx] == '1') && (destroy + 1 <= k) && !visited[destroy + 1][ny][nx]) {
                if (is_night) {
                    if (!flag) {
                        visited[destroy][cur.y][cur.x] = visited[destroy][cur.y][cur.x] + 1;
                    }
                    q.push({ destroy, !is_night, cur.y,cur.x });
                    flag = true;
                }
                else {
                    visited[destroy + 1][ny][nx] = visited[destroy][cur.y][cur.x] + 1;
                    q.push({ destroy + 1,!is_night, ny, nx });
                }
            }
        }

    }
\
    for (int i = 0; i <= k; i++) {
        if (visited[i][n - 1][m - 1]) {
            ans = min(ans, visited[i][n - 1][m - 1]);
        }
    }

    if (ans == 1000001)
        cout << -1 << '\n';
    else
        cout << ans << '\n';

    return 0;
}