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
abdelhameedddd:
20180723 03:52:27
ac 

rohitnarayan:
20180701 15:57:25
hint  use multisource BFS!! :) 

rajcoolaryan:
20180628 12:32:02
ac in one go


summer_2:
20180626 15:42:04
I am getting WA while using brute force all TC worked for me Help!


nadstratosfer:
20180605 03:05:33
Awesome problem. I remember looking at it a year ago, unable to figure out a decent approach; tonight I immediately came up with 2 different ones, invented third in the process and have a vague idea how to do it better still. AC with each  love problems that allow such experiments. No points for this, but a lot of fun for sure! 

grylls:
20180306 18:50:27
AC through DP but i was thinking of multi source BFS Solution. if anyone submitted Plz send the code at gmail


hai_dee:
20180222 10:53:28
Great question, but PLEASE change the wording regarding the input format. It cost me 3 RE's :( 

nitishk24:
20180105 02:11:33
DP solution: Break in 2 parts, one traversal can pass traverses bottom right while another up left


frozen7:
20171220 09:02:47
simple multi source bfs question 

karthik1997:
20171217 17:39:51
Nice Problem Try using 2pass DP , (top down and bottom up passes ) and its complexity is O(M*N) . Would never go TLE , if m and n are increased by 100 folds => to 10000 , while bfs surely results in TLE. Last edit: 20171217 17:41:34 
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 