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

[FPaul]

Хочется оптимизации, как с алгоритмами Манакера, Флойда - строится дополнительный массив(ы) или матрица(цы), а из них всё простенько извлекается. И в целом быстрее.
Плюс наноалгоритм своего имени.
Ну вот. Придется начинать.

[Poma][a]

Добрался до 10-го

#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())
    {
        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;
                        st _t;
                    _t.x = t.x+step[i].x; _t.y = t.y+step[i].y; _t.w = t.w;
                        temp.push(_t);
                }
                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;
}

[FPaul]

Похвастаюсь
Я там получился Неизвестным (и изменить ничего не могу).
Pascal 0,109 - 1220 Кб
Реализация - без очереди, нашел 0 и пускаю круги, каждый круг проверяю на количество ненулевых элементов.
-----------
Впечатления в сравнении с тимусом скорее негативные - TurboPascal, нет условной компиляции, подтверждающей проверку на сайте, рейтинг по размеру исходника.

[BDA]

Вы тут так упорно решаете задачку, что пришлось присоединиться
C++ 0,115 - 812 Кб, размер: 376
Без очереди, круги

[FPaul]

BDA! Впечатлён!
"Accepted 0,106 60 Кб"? Динамические массивы?
"Accepted 0,011 60 Кб"? Чем можно так ускориться? Тема задачи "Динамическое программирование" - но как?

И где "потерялся" Poma][a?

[Poma][a]

Спать ушел, не все с Вами "круги пускать"

Должен быть тест, который будет слишком долго работать на Ваших кругах

А вот смортите.. Вы круги пускаете по изначальному массиву? или же по конечному?

Я там получился Неизвестным (и изменить ничего не могу).

В паспорте(тамошнем) меняется

UPDATE
Дошло..
Я лажаю на тесте

3
1 0 1
1 0 1
1 0 1

А Вы крутите по начальному..

[FPaul]

У меня 2 массива - на 1 пускаю круги, а во 2 вношу изменения. Можно попробовать и, как предлагал Аватар

Массив один, забитые нули заполнить отрицательными что бы не путаться, выводить Abs

. Но в условии не гарантируются положительные числа.

Кто-то сегодня всю ночь успешно тестировал варианты решения задачи, причём его решение, судя по логам, впервые он нашёл ещё в феврале прошлого года. Так у него результаты впечатляли "Accepted 0,011 60 Кб". Чем он брал?

[Аватар]

Дана матрица A размером NxN, заполненная неотрицательными целыми числами

гарантируется

[FPaul]

Увы мне...

[Poma][a]

Фух..
Вот и я присоединился к Вашему обществу..

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

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

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

struct _step
{
	int x, y;
	friend bool operator == (const _step& a, const _step& b);
	friend bool operator != (const _step& a, const _step& b);
};

bool operator == (const _step& a, const _step& b)
{
	return a.x == b.x && a.y == b.y;
}

bool operator != (const _step& a, const _step& b)
{
	return !(a == b);
}

_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, -1)), p(n + 2, vector<int>(n + 2, -1)), p1(n + 2, vector<int>(n + 2, -1));
	vector<vector<_step> > stp (n+2, vector<_step> (n+2));
	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];
				_t.ix = i; _t.iy = j;
				q.push(_t);
				_step tt;
				tt.x = _t.x; tt.y = _t.y;
				stp[i][j] = tt;
				p[i][j] = v[i][j];
				p1[i][j] = 0;
			}
		}

	while (!q.empty() && k > 0)
	{
		queue<st> temp;

		while (!q.empty())
		{
			st t = q.front();
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				_step tt = stp[t.ix][t.iy];
		
				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 && stp[t.x + step[i].x][t.y + step[i].y] != tt)
				{
					p[t.x + step[i].x][t.y + step[i].y] = -1;
					st _t;
					_t.x = t.x + step[i].x; _t.y = t.y + step[i].y; _t.w = t.w;
					_t.ix = t.ix; _t.iy = t.iy;
					temp.push(_t); continue;
				}
				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;
					_t.ix = t.ix; _t.iy = t.iy;
					temp.push(_t);
					p[t.x + step[i].x][t.y + step[i].y] = t.w;
					stp[t.x + step[i].x][t.y + step[i].y].x = _t.ix;
					stp[t.x + step[i].x][t.y + step[i].y].y = _t.iy;
					continue;
				}
			}
		}
		q = temp;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << max(0, p[i][j]) << " ";
		cout << endl;
	}
	return 0;
}