롤러스케이트를 탄 소들

면접 대비

시간 제한1초메모리 제한128 MB

요약

열린 격자 칸만 지나 (1,1)에서 (R,C)까지 가는 최단 경로를 찾고, 같은 길이면 칸 수열이 사전순으로 가장 작은 경로를 출력한다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 행렬, 최단 경로
정답자: 아직 제출이 없습니다

문제

드디어 오랜 부탁 끝에 Farmer John이 마음을 돌려 소 떼 전체를 위해 롤러스케이트를 사 주었습니다. 농장의 많은 부분은 롤러스케이트를 타기에 아주 좋지만, 일부 칸에는 바위가 너무 많아 스케이트로는 지나갈 수 없습니다.

농장은 $R$ 개의 행과 $C$ 개의 열로 이루어진 격자로 나타냅니다 ( $1 \le R \le 113$ , $1 \le C \le 77$ ). 밥 먹을 시간이 된 Bessie는 칸 $(1, 1)$ 에 있고, 칸 $(R, C)$ 에 있는 외양간으로 돌아가려고 합니다. Bessie는 바위가 없는 칸들 사이를 상하좌우로 인접한(대각선은 제외) 칸으로만 이동할 수 있습니다. $(1, 1)$ 에서 $(R, C)$ 까지 갈 수 있는 방법이 적어도 하나 존재함이 보장됩니다.

여기서 $(r, c)$ 는 위에서 $r$ 번째 행, 왼쪽에서 $c$ 번째 열에 있는 칸을 뜻합니다.

입력

첫째 줄: 공백으로 구분된 두 정수 $R$ 과 $C$ 가 주어집니다.
다음 $R$ 개의 줄: 각 줄에는 공백 없이 $C$ 개의 문자가 주어집니다. 각 문자는 Bessie가 스케이트를 탈 수 있는 칸을 뜻하는 '.' 또는 바위가 너무 많은 칸을 뜻하는 '*' 중 하나입니다. 이 줄들 중 $i$ 번째 줄의 $j$ 번째 문자가 칸 $(i, j)$ 를 나타냅니다. 칸 $(1, 1)$ 과 $(R, C)$ 는 항상 '.'입니다.

출력

$(1, 1)$ 에서 $(R, C)$ 까지 가는 가장 짧은 경로를 출력합니다. 경로란 $(1, 1)$ 에서 시작해 $(R, C)$ 에서 끝나는 칸들의 수열로, 이웃한 두 칸은 변을 공유하도록 상하좌우로 인접해야 하며, 어떤 칸도 바위여서는 안 됩니다. 가장 짧은 경로는 포함된 칸의 수가 가장 적은 경로입니다.

가장 짧은 경로가 여러 개라면, 그중 사전순으로 가장 앞서는 경로를 출력합니다. 두 경로를 칸의 수열로 보고 앞에서부터 비교하며, 각 칸을 $(\text{행}, \text{열})$ 쌍으로 보아 행을 먼저, 그다음 열을 비교합니다.

경로의 각 칸을 한 줄에 하나씩, 공백으로 구분된 두 정수 '행 열' 형태로 출력합니다. 첫 줄은 반드시 '1 1'이어야 하고, 마지막 줄은 반드시 'R C'(즉 $R$ 과 $C$ )여야 합니다.

예제6

예제 1

입력

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

예상 출력

예제 2
입력
```
1 1
.
```
예상 출력
```
1 1
```
예제 3
입력
```
1 5
.....
```
예상 출력
```
1 1
1 2
1 3
1 4
1 5
```
예제 4
입력
```
5 1
.
.
.
.
.
```
예상 출력
```
1 1
2 1
3 1
4 1
5 1
```
예제 5
입력
```
2 2
..
..
```
예상 출력
```
1 1
1 2
2 2
```
예제 6
입력
```
3 3
...
.*.
...
```
예상 출력
```
1 1
1 2
1 3
2 3
3 3
```