All Submissions


The city of Whoo-Ville is under attack. In order for the inhabitants to stay safe they must go to the nearest building declared as a shelter. But some of the residents don't know which shelter is the closest one. Write a program to determine the distance from each building to the nearest shelter if the city's buildings are represented as 1 or 0, 1 for a building which is a shelter and 0 for a building which is not.
The distance can be calculated as follows:

If (x1,y1) is the location of the building in question and (x2,y2) is the location of a shelter, then the distance between the two is :

dist=|x2-x1|+|y2-y1|

Input Specification

The first line of input indicates the number of test cases. In the first line of each test case n and m are given separated by a single space. The next n lines of the test contains a zero-one word of length m.

Output Specification

In the ith line of each test case there should be m space separated integers i.e. f(i,1)...f(i,m) where f(i,j) is the distance of the building at location (i,j) from the nearest shelter.

Sample Input


2
3 4
0001
0011
0110
5 6
000000
010101
001100
010000
000101


Sample Output


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


Constraints : 1<=n,m<=200 and at least one building must be a shelter

Time Limit : 2 seconds

Problem Setter : Neesha Sinha

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 3 Second(s)
Score: 25 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0