문제
JOI 시는 남북으로 \(H\)킬로미터, 동서로 \(W\)킬로미터인 직사각형이고, \(H \times W\)개의 \(1\)킬로미터 사방 작은 칸으로 나뉘어 있다. 북쪽에서 \(i\)번째, 서쪽에서 \(j\)번째 칸을 \((i, j)\)로 나타낸다. 각 칸은 하늘에 구름이 있거나 없거나 둘 중 하나이다. 모든 구름은 \(1\)분이 지날 때마다 \(1\)킬로미터 동쪽으로 이동한다. 오늘은 날씨가 아주 좋아서, JOI 시 밖에서 시내로 구름이 들어오지는 않는다. 지금 각 칸 하늘에 구름이 있는지 없는지 알려져 있다. 기상 예보관인 당신은 각 칸에 대해, 지금부터 몇 분 뒤에 처음으로 그 칸 하늘에 구름이 오는지를 예측하게 되었다. 각 칸에 대해, 지금부터 몇 분 뒤에 처음으로 그 칸 하늘에 구름이 오는지 구하라. |
입력
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_H\)
- 입력은 \(1+H\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\)가 공백 하나로 구분되어 주어진다.
- 이어지는 \(H\)줄 가운데 \(i\)번째 줄(\(1 \le i \le H\))에는 길이 \(W\)의 문자열이 공백 없이 주어진다. \(j\)번째 문자(\(1 \le j \le W\))는 칸 \((i, j)\) 하늘에 지금 구름이 있는지를 나타낸다. 구름이 있으면 문자 c, 없으면 문자 . 이다.
- \(1 \le H \le 100\)
- \(1 \le W \le 100\)
출력
다음 형식으로 출력한다.
\(H\)줄을 출력하고, 각 줄은 공백 하나로 구분된 정수 \(W\)개이다. \(i\)번째 줄의 \(j\)번째 정수(\(1 \le i \le H\), \(1 \le j \le W\))는 지금부터 몇 분 뒤에 처음으로 칸 \((i, j)\) 하늘에 구름이 오는지를 나타낸다. 지금 이미 구름이 있으면 \(0\)을, 아무리 기다려도 구름이 오지 않으면 \(-1\)을 출력한다.
각 줄의 맨 앞과 맨 뒤에 여분의 공백을 넣지 않는다.
예시 1
입력
3 4
c..c
..c.
....
출력
0 1 2 0
-1 -1 0 1
-1 -1 -1 -1
예시 2
입력
6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...
출력
-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3