2014
03-01

# Mine

Some mines are buried in the minefield. You need to find them all. The whole minefield is divided into n*m square regions. Each region has at most one mine. If there is no mine in a region, you can use a detector in this square area. The detector will tell you the total number buried mines in the eight regions around it. Now some regions of the entire minefield have been confirmed to be clear, and in these regions detector results are known too. The total number of mines in minefield is also known. And I hope you can determine the specific location of all buried mines.

There are multiple test cases.

The first line contains a case number t.

For each case, the first line contains three integers. The size of the minefield , n (2<n<10) and m (2<m<10), the total number of the mines buried in the minefield k(1<k<=10).

The next n lines contains m characters which describe the situation of the minefield. Each character corresponds to a region. The character ‘#’ means the region is unknown, otherwise it is ’0 ‘~ ’8′, showing the detector results in this region. The input data are legitimate, which means the results of detectors are accurate and reliable.

There are multiple test cases.

The first line contains a case number t.

For each case, the first line contains three integers. The size of the minefield , n (2<n<10) and m (2<m<10), the total number of the mines buried in the minefield k(1<k<=10).

The next n lines contains m characters which describe the situation of the minefield. Each character corresponds to a region. The character ‘#’ means the region is unknown, otherwise it is ’0 ‘~ ’8′, showing the detector results in this region. The input data are legitimate, which means the results of detectors are accurate and reliable.

3
4 4 3
####
#111
111#
001#
3 3 2
##1
#21
#10
3 3 2
1#1
2#2
1#1 

111*
*111
1111
001*

NO

1*1
222
1*1