비트맵

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

요약

n x m 비트맵의 모든 검은 픽셀에 대해 가장 가까운 흰 픽셀까지의 맨해튼 거리를 출력한다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

$n \times m$ 크기의 직사각형 비트맵이 주어진다. 비트맵의 각 픽셀은 흰색 또는 검은색이며, 적어도 하나의 픽셀은 흰색이다. $i$ 번째 행 $j$ 번째 열에 있는 픽셀을 $(i, j)$ 로 나타낸다.

두 픽셀 $p_1 = (i_1, j_1)$ 과 $p_2 = (i_2, j_2)$ 사이의 거리는 다음과 같이 정의한다.

$d(p_1, p_2) = |i_1 - i_2| + |j_1 - j_2|$

모든 픽셀에 대해 가장 가까운 흰색 픽셀까지의 거리를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 공백 하나로 구분되어 주어진다 ( $1 \le n \le 182$ , $1 \le m \le 182$ ).

이어지는 $n$ 개의 줄에는 각각 길이가 $m$ 인 0과 1로 이루어진 문자열이 하나씩 주어지며, 이는 비트맵의 한 행을 나타낸다. 비트맵의 $i$ 번째 행을 나타내는 문자열에서 $j$ 번째 문자가 1이면, 그리고 오직 그때만 픽셀 $(i, j)$ 가 흰색이다 ( $1 \le i \le n$ , $1 \le j \le m$ ).

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 $m$ 개의 정수 $f(i, 1), \dots, f(i, m)$ 을 공백 하나로 구분하여 출력한다. 여기서 $f(i, j)$ 는 픽셀 $(i, j)$ 에서 가장 가까운 흰색 픽셀까지의 거리이다.

예제4

예제 1

입력

예상 출력

3 2 1 0
2 1 0 0
1 0 0 1

예제 2
입력
```
1 1
1
```
예상 출력
```
0
```
예제 3
입력
```
1 5
00100
```
예상 출력
```
2 1 0 1 2
```
예제 4
입력
```
2 2
11
11
```
예상 출력
```
0 0
0 0
```