14923 미로 탈출

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

14923번: 미로 탈출

벽 부수고 이동하기와 유사한 문제였다. 간만에 풀어보았는데 좋은 연습이 되었다. 실수로 board에 z축을 추가해서 맞왜틀을 했었다...

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

int board[1003][1003];
int dist[1003][1003][2];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
queue<tuple<int,int,int>> Q;
int n,m,Hx,Hy,Ex,Ey;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>Hy>>Hx>>Ey>>Ex;
    Hx--; Hy--; Ex--; Ey--;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>board[i][j];
            dist[i][j][0]=-1;
            dist[i][j][1]=-1;
        }
    }
    dist[Hy][Hx][0]=0;
    Q.push({Hy,Hx,0});
    while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        int curY,curX,curW; tie(curY,curX,curW)=cur;
        int curDist=dist[curY][curX][curW];

        //도착했다면 END
        if(curY==Ey && curX==Ex){
            cout<<curDist<<'\n';
            return 0;
        }

        for(int dir=0;dir<4;dir++){
            int ny=curY+dy[dir];
            int nx=curX+dx[dir];
            int nw=curW;
            if(ny<0||nx<0||ny>=n||nx>=m) continue;
            //벽을 만났다면 깨고 봄
            if(board[ny][nx]==1) nw++;
            //벽을 2회 이상 부쉈거나 이미 갔던 곳이면 continue
            if(nw>1 || dist[ny][nx][nw]!=-1) continue;
            dist[ny][nx][nw]=curDist+1;
            Q.push({ny,nx,nw});
        }
    }
    cout<<-1;
    return 0;
}