#1958 지뢰를 피하여

100  1 s   128 MB  

Description

지뢰밭에서 지뢰를 피해 목적지까지 가장 빨리 도달하는 길을 찾는 어플리케이션을 개발하려고 한다. 이를 위해서 먼저 지뢰에 영향을 받지 않는 안전한 영역이 어디인지를 찾는 프로그램을 먼저 작성해 보자. 지뢰밭에는 두 가지 종류가 지뢰가 있는데 성능이 향상되어 지뢰 자체를 밟는 것뿐만 아니라 그 주변을 밟아도 터지는 첨단 지뢰이다. 한 가지 지뢰는 ‘*’로 표시되는 지뢰인데 이는 지뢰 자체와 그 주변을 밟기만 해도 터지는 지뢰이다. 또한 ‘#’으로 표시되는 지뢰는 센서가 더욱 예민해서 지뢰 자체는 물론 그 주변과 주변의 주변까지 밟기만 해도 폭발하는 고성능 지뢰이다.

지뢰밭이 주어질 경우에 지뢰의 종류에 따라 지뢰 주변 셀(지뢰가 존재하는 셀에 가로, 세로, 대각선으로 인접한 셀), 지뢰 주변의 주변 셀(지뢰 주변 셀에 가로, 세로, 대각선으로 인접한 셀)까지를 위험 지역으로 표시하고 지뢰의 영향을 받지 않는 셀을 안전한 지역으로 표시해 주는 프로그램을 작성하자.

Input

입력의 처음에는 테스트 케이스의 개수T(1 ≤ T ≤ 10)가 입력되며, 다음 줄 부터 T개의 테스트 케이스가 입력된다.

각 테스트 케이스의 첫 줄에ㅐ는 M x N 크기(M: 높이, N: 폭)의 지뢰밭을 의미하는 M, N(3<= M, N <=20)이 입력되며, 다음 줄 부터 M개의 줄에 M x N 크기의 지뢰밭이 입력된다.

지뢰가 없는 지역은 ‘.’으로 표시되며 일반지뢰는 ‘*’, 고성능 지뢰는 ‘#’으로 표시된다.

Output

각 테스트 케이스마다 지뢰의 영향을 받지 않는 안전한 자리는 ‘0’으로, ‘*’로 표시되는 일반 지뢰의 영향을 받는 주변 자리와 ‘#’으로 표시되는 고성능 지뢰의 영향을 받는 주변 자리와 주변의 주변 자리는 ‘1’로 구분하여 M x N 크기로 출력한다. 지뢰가 있는 자리는 원래대로 ‘*’과 ‘#’을 출력한다. 

Sample Input

Sample Output

2
3 4
....
.*..
....
5 5
*....
....*
.....
.....
#....
1110
1*10
1110
*1011
1101*
11111
11100
#1100

Source

동의대학교 멀티미디공학과 우영운(2011년 12월 8일)