문제
강희는 정신을 차려보니 낯선 유령선에 납치당해 있었다. 강희는 유령들이 자고 있는 낮 시간에 몰래 유령선에 있는 구명보트를 이용해 탈출하려고 한다.
유령선의 갑판은 동일한 크기의 정사각형 모양 판자가 가로로 W개, 세로로 H개 이어진 모양으로 되어 있다. 강희는 현재 서 있는 위치에서 상하좌우로 움직일 수 있다. 유령선은 매우 낡았기 때문에 강희가 딛고 있는 판자를 벗어나면 판자가 부서지고 만다. 심지어 이미 부서져 있는 판자도 존재한다. 물론 강희는 유령이 아니기 때문에 부서진 판자는 걸어서 지나갈 수 없다.
판자가 너무 많이 부서지면 유령들이 화를 내기 때문에 강희는 가장 작은 개수의 판자를 파괴하면서 유령선에서 탈출하려고 한다. 강희가 유령선에서 탈출하는 것을 돕는 프로그램을 작성하자.
시간제한: 1초
입력
첫 줄에 두 정수 W(2<=W<=1500)와 H(2<=H<=1500)가 공백을 사이에 두고 주어진다. 그 다음 줄부터 H줄마다 각각 W개의 문자가 주어진다.
각 문자는 X, O, S, E 중 하나며 전체 문자들 중 S와 E는 정확히 하나임이 보장된다.
X는 처음부터 부서진 판자를 나타낸다.
O는 강희가 밟고 지나갈 수 있지만, 밟은 이후 부서지는 판자를 나타낸다.
S는 처음 강희가 서 있는 판자의 위치를 나타낸다.
E는 유령선의 구명보트 위치를 나타낸다.
출력
강희가 판자를 최소 개수로 파괴하면서 유령선에서 탈출할 때 파괴되는 판자의 개수를 첫 줄에 출력하라.
만약 강희가 유령선에서 탈출할 수 있는 방법이 없는 경우, -1을 출력하라.
힌트
예제 입력 1
4 3
OOSO
OXXO
OOEO
예제 출력 1
4
예제 설명 1
총 두 가지 탈출 경로가 존재한다.
강희가 (좌, 좌, 하, 하, 우, 우)로 움직이는 경우 6개의 판자가 부서진다.
강희가 (우, 하, 하, 좌)로 움직이는 경우 4개의 판자가 부서진다.
따라서 답은 4이다.
예제 입력 2
3 3
EXX
XSO
OOX
예제 출력 2
-1
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 64 65 66 67 68 69 70 71 72 73 74 75 | #include <iostream>#include <fstream>#include <stack>#include <algorithm>#include <limits.h>#include <queue>using namespace std; struct Node { int x; int y;}; int W, H;int M[1501][1501]; Node S, E;int di[4][2] = { { 0,-1 },{ 1,0 },{ 0,1 },{-1,0 } }; void BFS() { queue<Node> checkQ; checkQ.push(S); while (!checkQ.empty()) { Node curNode = checkQ.front(); checkQ.pop(); for (int i = 0; i < 4; i++) { int nextX = curNode.x + di[i][0]; int nextY = curNode.y + di[i][1]; if (nextX > 0 && nextX <= W && nextY > 0 && nextY <= H) { if (M[curNode.x][curNode.y] + 1 < M[nextX][nextY]) { M[nextX][nextY] = M[curNode.x][curNode.y] + 1; checkQ.push({ nextX , nextY }); } } } } } int main() { cin >> W >> H; char info[1501]; cin.getline(info, 1501, '\n'); for (int h = 1; h <= H; h++) { cin.getline(info, 1501,'\n'); for (int w = 0; w < W; w++) { M[w + 1][h] = INT_MAX; if (info[w] == 'S') { S.x = w + 1; S.y = h; M[S.x][S.y] = 0; } else if (info[w] == 'E') { E.x = w + 1; E.y = h; } else if (info[w] == 'X') { M[w + 1][h] = 0; } } } BFS(); if (M[E.x][E.y] == INT_MAX) { cout << -1 << endl; } else { cout << M[E.x][E.y] << endl; } return 0;} |