BITMAP  Bitmap
There is given a rectangular bitmap of size n*m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in ith line and jth column is called the pixel (i,j). The distance between two pixels p_{1}=(i_{1},j_{1}) and p_{2}=(i_{2},j_{2}) is defined as:
Task
Write a program which:
 reads the description of the bitmap from the standard input,
 for each pixel, computes the distance to the nearest white pixel,
 writes the results to the standard output.
Input
The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is a pair of integer numbers n, m separated by a single space, 1<=n <=182, 1<=m<=182. In each of the following n lines of the test case exactly one zeroone word of length m, the description of one line of the bitmap, is written. On the jth position in the line (i+1), 1 <= i <= n, 1 <= j <= m, is '1' if, and only if the pixel (i,j) is white.
Output
In the ith line for each test case, 1<=i<=n, there should be written m integers f(i,1),...,f(i,m) separated by single spaces, where f(i,j) is the distance from the pixel (i,j) to the nearest white pixel.
Example
Sample input: 1 3 4 0001 0011 0110 Sample output: 3 2 1 0 2 1 0 0 1 0 0 1
hide comments
egor091:
20200619 16:45:24
AC in one go


yash_999:
20200616 10:03:06
can be done without multisource bfs using only bfs shortest path with a little optimization ran in 0.5 s


gaur_gaur:
20200531 08:44:05
simple mutisource bfs question :) 

joaoabrantes:
20200528 14:52:57
Please take care after output each test, you need to read a empty line after every output, otherwise you gonna get RE 

prantoru:
20200514 07:30:52
who still could't solve the problem, just goto geeksforgeeks and read the article about multisouce bfs and solve the problem.... :) 

prantoru:
20200514 06:50:24
what is the maximum value of t....? _ 

shuhbo:
20200509 20:03:17
Simple logic. You can solve without bfs and dfs. 

abhishek_251:
20200425 08:38:58
if you're using multisource bfs keep in mind don't use pair,map etc. theres high chances that you will get TLE. And also no need of visited{true} array.


aman5898:
20200410 15:49:53
Ac in one go :p


khauf007:
20200410 11:41:28
I am getting TLE repeatedly using multisource bfs i am not able to figure out the problem

Added by:  Piotr Ćowiec 
Date:  20040913 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  6th Polish Olympiad in Informatics, stage 2 