## BITMAP - Bitmap

no tags

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 i-th line and j-th column is called the pixel (i,j). The distance between two pixels p1=(i1,j1) and p2=(i2,j2) is defined as:

d(p1,p2)=|i1-i2|+|j1-j2|.

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 <=1821<=m<=182. In each of the following n lines of the test case exactly one zero-one word of length m, the description of one line of the bitmap, is written. On the j-th position in the line (i+1), 1 <= i <= n1 <= j <= m, is '1' if, and only if the pixel (i,j) is white.

### Output

In the i-th 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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
using namespace std;

string a[200];
int ans[200][200], q[200 * 200 * 2], n, m, s;
int dx[] = {0 , 0 , 1 , -1}, dy[] = {1 , -1, 0 , 0};

void bfs()
{
for(int i=0;i<s;i+=2)
{
int cx=q[i];
int cy=q[i+1];
for(int j=0;j<4;j++)
{
int xx=cx+dx[j];
int yy=cy+dy[j];
if(xx < 0 || yy < 0 || xx >= n || yy >= m || ans[xx][yy] != -1) continue;
ans[xx][yy] = ans[cx][cy] + 1;
q[s++] = xx;
q[s++] = yy;
}
}
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < m; j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
int main()
{
long long t;
cin>>t;
while(t--)
{
memset(ans, 255, sizeof ans);
s=0;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
for(int j=0;j<m;j++)
{
if(a[i][j]=='1')
{
ans[i][j]=0;
q[s++]=i;
q[s++]=j;
}
}
}
bfs();
}
}``````
Copy The Code &

Input

cmd
1
3 4
0001
0011
0110

Output

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

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.*;
import java.util.*;
class BITMAP{
public static void main(String[] args) throws Exception{
Parser in = new Parser(System.in);
StringBuilder string = new StringBuilder();
int num = in.nextInt();
for(int z = 0; z < num; z++){
int rows = in.nextInt();
int cols = in.nextInt();
char[][] grid = new char[rows+2][cols+2];
int[][] result = new int[rows+2][cols+2];
int[] xValues = {1, -1, 0, 0};
int[] yValues = {0, 0, 1, -1};

for(int a = 0; a < cols+2; a++){
grid[0][a] = '#';
grid[rows+1][a] = '#';
}

Bit current = null;
boolean[][]visited = new boolean[rows+2][cols+2];

for(int j = 1; j < rows+1; j++){
String line = in.next();
grid[j][0] = '#';
for(int k = 1; k < cols+1; k++){
grid[j][k] = line.charAt(k-1);
result[j][k] = 500;
if(grid[j][k] == '1'){
visited[j][k] = true;
}
}
grid[j][cols+1] = '#';
}

while(!queue.isEmpty()){
current = queue.remove();
result[current.x][current.y] = Math.min(current.distance, result[current.x][current.y]);
for(int m = 0; m < 4; m++){
int x = current.x+xValues[m];
int y = current.y+yValues[m];
if(!visited[x][y] && grid[x][y] != '#'){
visited[x][y] = true;
}
}
}

for(int rowNum = 1; rowNum < rows+1; rowNum++){
for(int colNum = 1; colNum < cols+1; colNum++){
if(colNum == cols){
string.append(result[rowNum][colNum] + "\n");
}else{
string.append(result[rowNum][colNum] + " ");
}
}
}
string.append("\n");
}
System.out.print(string);
}

static class Bit{
public int x;
public int y;
public int distance;

public Bit(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}
}
}

class Parser
{
final private int BUFFER_SIZE = 1 << 16;

private DataInputStream din;
private byte[] buffer;

public Parser(InputStream in)
{
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
}

public long nextLong() throws Exception
{
long ret = 0;
while (c <= ' ') c = read();
boolean neg = c == '-';
do
{
ret = ret * 10 + c - '0';
} while (c > ' ');
if (neg) return -ret;
return ret;
}

public String next() throws Exception
{
StringBuilder ret =  new StringBuilder();
while (c <= ' ') c = read();
do
{
ret = ret.append((char)c);
} while (c > ' ');
return ret.toString();
}

public int nextInt() throws Exception
{
int ret = 0;
while (c <= ' ') c = read();
boolean neg = c == '-';
do
{
ret = ret * 10 + c - '0';
} while (c > ' ');
if (neg) return -ret;
return ret;
}

private void fillBuffer() throws Exception
{
if (bytesRead == -1) buffer[0] = -1;
}

{
return buffer[bufferPointer++];
}
}``````
Copy The Code &

Input

cmd
1
3 4
0001
0011
0110

Output

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