쉬운 최단거리

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

요약

하나의 목표 칸과 막힌 칸이 있는 격자에서 상하좌우 이동으로 각 열린 칸에서 목표까지의 최단 거리를 구한다.

난이도: 쉬움10점 중 3점
유형: BFS, 그래프, 행렬
정답자: 아직 제출이 없습니다

문제

지도가 주어진다. 모든 칸에서 목표 지점까지의 최단 거리를 구하여라.

문제를 쉽게 만들기 위해 이동은 상하좌우 네 방향으로만 할 수 있다고 하자. 인접한 칸으로 한 번 움직이면 거리가 1 늘어나고, 갈 수 없는 땅은 지나갈 수 없다.

입력

첫째 줄에 지도의 크기 $n$ 과 $m$ 이 주어진다. $n$ 은 세로 크기, $m$ 은 가로 크기다. ( $2 \le n \le 1000$ , $2 \le m \le 1000$ )

다음 $n$ 개 줄에 각각 $m$ 개의 숫자가 공백으로 구분되어 주어진다. 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점이다. 2는 입력 전체에 정확히 한 개 있다.

출력

$n$ 개 줄에 각각 $m$ 개의 수를 공백으로 구분해 출력한다. $r$ 번째 줄의 $c$ 번째 수는 $r$ 행 $c$ 열 칸에서 목표 지점까지의 최단 거리다.

갈 수 없는 땅인 칸은 0을 출력한다. 갈 수 있는 땅이지만 목표 지점에 도달할 수 없는 칸은 -1을 출력한다. 목표 지점 자체는 0을 출력한다.

예제2

예제 1

입력

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예상 출력

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

예제 2

입력

4 6
2 1 1 1 1 1
1 1 0 0 0 1
1 1 0 1 0 1
1 1 0 0 0 1

예상 출력

0 1 2 3 4 5
1 2 0 0 0 6
2 3 0 -1 0 7
3 4 0 0 0 8