[14923번] 미로 탈출

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

3차원 배열을 만들어 y,x,magic 여부를 상태로 두고 BFS를 돌리면 문제를 해결 할 수 있다.

벽부수고 이동하기 문제와 아주 유사한 문제이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream> #include <cstdio> #include <algorithm> #include <queue>   using namespace std;   typedef pair<int, int> pii;   bool visit[1002][1002][2]; int arr[1002][1002];   int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,-1,0,1 };   queue<pair<pii, pii>> q;   int main() {     int n, m;     scanf("%d %d", &n, &m);       int sx, sy, ex, ey;     scanf("%d %d %d %d", &sy, &sx, &ey, &ex);       for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             scanf("%d", &arr[i][j]);       q.push({ {sy - 1, sx - 1},{0, 1} });       while (!q.empty()) {         int y = q.front().first.first;         int x = q.front().first.second;         int cnt = q.front().second.first;         int magic = q.front().second.second;                  q.pop();           if (y == ey - 1 && x == ex - 1)             return !printf("%d\n", cnt);           if (visit[y][x][magic])             continue;           visit[y][x][magic] = true;           for (int i = 0; i < 4; i++) {             int ny = dy[i] + y;             int nx = dx[i] + x;               if (0 <= ny && ny < n && 0 <= nx && nx < m) {                 if (arr[ny][nx] && magic)                     q.push({ {ny,nx}, {cnt + 1, 0} });                 if (!arr[ny][nx])                     q.push({ {ny,nx}, {cnt + 1, magic} });             }         }       }       printf("-1\n");     return 0; } Colored by Color Scripter

cs