10049. Битовая карта

 

Задана прямоугольная битовая карта размером n * m. Каждая точка в ней белая или черная, хотя бы одна точка белая. Точку в i-ой строке и j-ом столпце назовем пикселем (i, j). Расстояние между двумя пикселями p1 = (i1, j1) и p2 = (i2, j2) определяется следующим образом:

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

Для каждой точки найдите расстояние до ближайшей белой точки.

 

Вход. Первая строка содержит количество тестов t. Первая строка каждого теста содержит два целых числа n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000). Каждая из следующих n строк содержит слово из нулей и единиц длины m, описывая битовую карту. В j-ой позиции i-ой строки (1 ≤ i ≤ n, 1 ≤ j ≤ m) находится 1 если только точка (i, j) белая.

 

Выход. В i-ой строке для каждого теста выведите m целых чисел f(i, 1), ..., f(i, m), разделенных пробелом, где f(i, j) – расстояние от точки (i, j) до ближайшей белой точки.

 

Пример входа

Пример выхода

1

3 4

0001

0011

0110

3 2 1 0

2 1 0 0

1 0 0 1

 

 

РЕШЕНИЕ

поиск в ширину

 

Анализ алгоритма

Занесем координаты всех единиц битовой карты в очередь. Запустим поиск в ширину из нескольких источников.

 

Реализация алгоритма

Определим рабочие константы.

 

#define INF 0x3F3F3F3F

#define MAX 1002

 

Битовую карту храним в массиве строк g. Кратчайшее расстояние от точки (i, j) до ближайшей единицы (массив кратчайших расстояний) сохраняем в dist[i][j].

 

string g[MAX];

int dist[MAX][MAX];

 

 Объявим очередь, которая будет содержать координаты точек.

 

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

 

Добавление точки (x, y) в очередь. Кратчайшее расстояние от нее до ближайшей точки с единицей равно d.

 

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

{

 

Если вышли за пределы прямоугольной области, то игнорируем точку.

 

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

 

Если значение dist[x][y] уже посчитано, то игнорируем точку.

 

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

 

Присваиваем значение dist[x][y] = d. Заносим точку (x, y) в очередь.

 

  dist[x][y] = d;

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

}

 

Функция bfs реализует поиск в ширину.

 

void bfs(void)

{

  int x, y;

 

Пока очередь не пуста, извлекаем из нее точку temp и кладем в очередь координаты ее четырех соседей.

 

  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);

  }

}

 

Основная часть программы. Читаем входные данные.

 

cin >> tests;

while (tests--)

{

  cin >> n >> m;

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

  {

    cin >> g[i];

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

  }

 

Инициализируем массив кратчайших расстояний значениями бесконечность.

 

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

 

Заносим в очередь q координаты всех точек с единицами.

 

  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;

    }

 

Запускаем поиск в ширину.

 

  bfs();

 

Выводим ответ – искомые расстояния.

 

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

  {

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

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

    cout << endl;

  }

}