Ближайшее число (Матрица)

[isst]

Всем доброго времени суток:

Дана матрица A размером NxN, заполненная неотрицательными целыми числами. Расстояние между двумя элементами Ai j и Ap q определено как |i - p| + |j - q|.

Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.

Ограничения: 1 <= N <= 200, 0 <= Ai j <= 1 000 000.

Входные данные
В первой строке содержится число N. Затем идут N строк по N чисел, разделённых пробелами и представляющих собой матрицу.

Выходные данные
Выводится N строк по N чисел, разделённых пробелами, - модифицированная матрица.

Примеры:
входные данные
3
5 0 0
0 0 0
0 0 6
выходные данные
5 5 0
5 0 6
0 6 6

Помогите, пож!

[FPaul]

Судя по условию - задача проверяется ejudge. Ты для себя участвуешь в онлайн-псевдоолимпиадах?

Тут решение ищется вариацией поиска в ширину (BSF) - почти волновым методом (алгоритм Ли). Лишь условия остановки слегка изменяются. В отличие от алгоритма Ли (из-за отсутствия препятствий) можно не хранить список ячеек фронта волны, а вычислять их.

Ознакомиться с алгоритмом Ли можно на Wikipedia и algolist.

Пробуй.
Или ты очень занят, а решать кому-то нужно? Я тоже занят - к нам в город приехал цирк Дю Солей, мы только это и обсуждаем с детьми.

[Poma][a]

Я тож за BFS.

В отличие от алгоритма Ли (из-за отсутствия препятствий) можно не хранить список ячеек фронта волны, а вычислять их.

Эм.. Что?
Если не хранить волну, то получим N^4.. А это точно не зайдет

И да, я бы начал так :
Пробежался бы по массиву, ставля перманентные 0
А дальше уже bfs

[FPaul]

А как уменьшить? Ведь, по существу, рассматриваются сочетания всех ячеек со всеми.
А не хранить фронт волны - просто отказ от двух массивов с перечнем ячеек текущей волны и с перечнем ячеек волны следующего шага. Т.к. можно получить аналитический вид 4 циклов for (ну добавив проверки на границы матрицы).
-----
Подумал ещё. Да, лучше хранить. Тогда при "неперспективности" направления будет уменьшаться длина волны=время выполнения.

[Poma][a]

Да не.. Ну на кой нам два массива.. Бахнем одну очередь. Будем крутить пока она не пуста, занимая соседние клетки

[FPaul]

Нет да пруф.

Хотя рядом с одним массивом. Но я его не понял - значит его не существует. Нет нет нет. Он, кажется, совсем без массива с волной. Там, что-то другое.
---------------
Ссылкозакидательство вместо аргументов.

[Poma][a]

Хотя рядом с одним массивом. Но я его не понял - значит его не существует. Нет нет нет. Он, кажется, совсем без массива с волной. Там, что-то другое.

Оно с очередью..

[FPaul]

Да, точно. Вариант С с очередью - эквивалентом объединения двух массивов (текущий фронт и будущий), но ускоренный из-за отсутствия копирования одного в другой.
Ну для нас всё уже ясно. Осталось уговорить кого-нибудь начать реализацию.

[Аватар]

Возле каждого нуля делать цикл по концентрическими квадратам под углом 45 градусов с учетом границы матрицы пока не найдется 1 или больше не нулевых в квадрате. В этом квадрате расстояние одинаковое до центра. Все. А то придумали, алгоритм Ли Массив один, забитые нули заполнить отрицательными что бы не путаться, выводить Abs

[Poma][a]

Вот..
Пока так..
Косяк на 8 тесте..
Проверял тут

#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");


struct st
{
	int x, y, w;	
};

struct _step
{
	int x, y;	
};

_step step[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main() {
	int n;
	cin >> n;
	
	vector<vector<int> > v(n+2, vector<int> (n+2)), p(n+2, vector<int> (n+2, -1)), p1(n+2, vector<int> (n+2, 0));
	queue<st> q;
	int k = 0;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
			if (v[i][j] == 0)
			{
				k++;
				p[i][j] = 0;
			}
			else
			{
				st _t;
				_t.x = i; _t.y = j; _t.w = v[i][j];
				q.push(_t);
				p[i][j] = v[i][j];
			}
		}	
	
	while (!q.empty() && k > 0)
	{
		queue<st> temp;
		vector<vector<int> > p1(n+2, vector<int> (n+2, -1));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				p1[i][j] = 0;
				
		while (!q.empty())
		{
			st t = q.front();
			q.pop();
			for (int i = 0; i < 4; i++)
				if (p[t.x+step[i].x][t.y+step[i].y] != 0 && p1[t.x+step[i].x][t.y+step[i].y] == p1[t.x][t.y]+1 && p[t.x+step[i].x][t.y+step[i].y] != t.w)
					p[t.x+step[i].x][t.y+step[i].y] = -1;
				else if (p[t.x+step[i].x][t.y+step[i].y] == 0)
				{
					k--;
					p1[t.x+step[i].x][t.y+step[i].y] = p1[t.x][t.y]+1;
					st _t;
					_t.x = t.x+step[i].x; _t.y = t.y+step[i].y; _t.w = t.w;
					temp.push(_t);
					p[t.x+step[i].x][t.y+step[i].y] = t.w;
				}
		
		}
		q = temp;
		
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << max(0, p[i][j]) << " ";
		cout << endl;
	}
	cout << endl;
	return 0;
}

Там вроде много лишнего есть..