10049. Bitmap

 

Rectangular bitmap of size n * m is given. 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|

For each pixel find the distance to the nearest white pixel.

 

Input. The number of test cases t is given in the first line, then t test cases follow. First line of each test case contains pair of integer numbers n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000). 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 ≤ i ≤ n, 1 ≤ j ≤ m) there is 1 if, and only if the pixel (i, j) is white.

 

Output. In the i-th line for each test case 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.

 

Sample input

Sample output

1

3 4

0001

0011

0110

3 2 1 0

2 1 0 0

1 0 0 1

 

 

SOLUTION

graphs, breadth first search

 

Algorithm analysis

Put the coordinates of all one’s in the bitmap into the queue. Start a breadth first search from multiple sources.

 

Algorithm realization

Declare the constants.

 

#define INF 0x3F3F3F3F

#define MAX 1002

 

Store the bitmap in an array of strings g. The shortest distance from the point (i, j) to the nearest one (array of shortest distances) is stored in dist[i][j].

 

string g[MAX];

int dist[MAX][MAX];

 

Declare a queue that will contain the coordinates of the points.

 

deque<pair<int, int> > q; // (x, y)

 

Adding point (x, y) to the queue. The shortest distance from it to the nearest point with one is d.

 

void Add(int x, int y, int d)

{

 

If you go beyond the rectangular area, then ignore the point.

 

  if ((x < 1) || (x > n) || (y < 1) || (y > m)) return;

 

If the value dist[x][y] has already been computed, then ignore the point.

 

  if (dist[x][y] != INF) return;

 

Assign the value dist[x][y] = d. Push the point (x, y) into the queue.

 

  dist[x][y] = d;

  q.push_back(make_pair(x, y));

}

 

Function bfs implements the breadth first search.

 

void bfs(void)

{

  int x, y;

 

While the queue is not empty, pop the point temp and push the coordinates of its four neighbors into the queue.

 

  while (!q.empty())

  {

    pair<int, int> temp = q.front();

    q.pop_front();

    x = temp.first; y = temp.second;

    Add(x + 1, y, dist[x][y] + 1); Add(x - 1, y, dist[x][y] + 1);

    Add(x, y + 1, dist[x][y] + 1); Add(x, y - 1, dist[x][y] + 1);

  }

}

 

The main part of the program. Read the input data.

 

cin >> tests;

while (tests--)

{

  cin >> n >> m;

 for (i = 1; i <= n; i++)

  {

    cin >> g[i];

    g[i] = " " + g[i];

  }

 

Initialize the array of shortest distances with infinity.

 

  memset(dist, 0x3F, sizeof(dist));

 

Push to the queue q the coordinates of all points with ones.

 

  for (i = 1; i <= n; i++)

  for (j = 1; j <= m; j++)

    if (g[i][j] == '1')

    {

      q.push_back(make_pair(i, j));

      dist[i][j] = 0;

    }

 

Run the breadth first serch.

 

  bfs();

 

Print the answer – the required distances.

 

  for (i = 1; i <= n; i++)

  {

    for (j = 1; j <= m; j++)

      cout << dist[i][j] << " ";

    cout << endl;

  }

}