백준 14923번 미로 탈출

문제 링크입니다: https://www.acmicpc.net/problem/14923

백준 2206번 벽 부수고 이동하기(http://jaimemin.tistory.com/650)와 똑같은 문제였습니다.

시작점과 탈출점이 지정되어 있고 인덱스를 1씩 증가시키는 점, 그리고 시작하는 칸을 세지 않는다는 점이 차이점이였습니다.

#include <iostream>

#include <string>

#include <queue>

using namespace std;

 

const int MAX = 1000 + 1;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };

 

int N, M;

pair<int, int> start, finish;

int graph[MAX][MAX];

int cache[MAX][MAX][2]; //마지막 2는 벽 뚫기 여부

 

int BFS(void)

{

        queue < pair<pair<int, int>, int>> q; //y, x, 벽 뚫기

        q.push(make_pair(start, 1)); //시작점, 벽 뚫기 가능

        cache[start.first][start.second][1] = 1;

 

        while (!q.empty())

        {

                 int y = q.front().first.first;

                 int x = q.front().first.second;

                 int block = q.front().second;

                 q.pop();

 

                 //도착하면

                 if (y == finish.first && x == finish.second)

                         return cache[y][x][block] - 1;

 

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = y + moveDir[i].y;

                         int nextX = x + moveDir[i].x;

 

                         if (1 <= nextY && nextY <= N && 1 <= nextX && nextX <= M)

                         {

                                 //벽이 있고, 벽을 아직 안 뚫었고, 방문하지 않았던 곳이라면

                                 if (graph[nextY][nextX] == 1 && block && cache[nextY][nextX][block - 1] == 0)

                                 {

                                          cache[nextY][nextX][block - 1] = cache[y][x][block] + 1;

                                          q.push(make_pair(make_pair(nextY, nextX), block - 1));

                                 }

                                 //벽이 없고 방문하지 않았던 곳이라면

                                 else if (graph[nextY][nextX] == 0 && cache[nextY][nextX][block] == 0)

                                 {

                                          cache[nextY][nextX][block] = cache[y][x][block] + 1;

                                          q.push(make_pair(make_pair(nextY, nextX), block));

                                 }

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        cin >> N >> M;

 

        cin >> start.first >> start.second;

        cin >> finish.first >> finish.second;

 

        for (int i = 1; i <= N; i++)

                 for(int j = 1; j <= M; j++)

                         cin >> graph[i][j];

 

        cout << BFS() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~