BOJ 2206 벽 부수고 이동하기

1 개요

BOJ 2206 벽 부수고 이동하기
2 C++

#include <bits/stdc++.h>
using namespace std;

int N, M;
int A[1001][1001] = {};
int visited[1001][1001][2] = {};

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

int bfs() {
    queue<tuple<int,int,int>> q;
    q.push({1,1,1});
    visited[1][1][1] = 1;
    int x, y, w, nx, ny, nw;
    while(!q.empty()) {
        tuple<int,int,int> t = q.front();
        q.pop();
        x = get<0>(t);
        y = get<1>(t);
        w = get<2>(t);
        if(x == M && y == N) return visited[x][y][w]; 
        for(int i=0; i<4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            nw = w;
            if(nx<1 || ny<1 || nx>M || ny>N) continue;
            if(A[nx][ny] == 1) {
                if(nw == 0) continue;
                nw = 0;
            }
            if(visited[nx][ny][nw]!=0) continue;
            q.push({nx,ny,nw});
            visited[nx][ny][nw] = visited[x][y][w] + 1;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    string temp;
    for(int y=1; y<=N; y++) {
        cin >> temp;
        for(int x=1; x<=M; x++) {
            A[x][y] = temp[x-1] - '0';
        }
    }
    cout << bfs();
}