Задача на поиск оптимального пути в матрице

[Poma][a]

Путешествие на хамелеоне

Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Вот уже несколько лет в Зазеркалье проводится удивительная игра – «Гонки на хамелеоне». Игра состоит в следующем: имеется игровое поле размером NxМ, каждая клетка поля покрашена в некоторый цвет, который кодируется целым числом от 1 до К (1<=K<=10000). Игрок, верхом на хамелеоне, должен пробраться из верхней левой клетки игрового поля в нижнюю правую, при этом потратив минимальное количество яблок. Яблоко приходится отдать хамелеону за то, что он меняет свой цвет, попав в клетку другого цвета. Изначально хамелеон находится в клетке с координатами (1, 1), и имеет ее цвет. Он может перемещаться в 4-х направлениях в любую соседнюю клетку, имеющую с текущей общую сторону. Задание: определите минимальное количество яблок, которое придется скормить хамелеону, чтобы осуществить указанное путешествие.
Формат ввода

Первая строка содержит два числа N и М – размер игрового поля (2<=N, М<=100). Далее следует N строк, каждая содержит по М целых чисел, разделенных пробелом, кодирующих цвет клетки (1..10 000).
Формат вывода

Выходной файл должен содержать целое неотрицательное число – минимальное количество яблок, которые придется скормить хамелеону.

Пример 1

5 4
1 1 1 2
2 1 2 3
3 1 2 3
1 1 3 3
1 1 1 3

Ответ :

1

Пример 2

5 4
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4
5 5 5 5

Ответ :

4

[Poma][a]

Утро доброе.
Задача, представленная выше была на городском этапе всероссийской олимпиады школьников по программированию(или информатике.. фиг знает)
Дык вот
Хотелось бы узнать, какое решение можно по праву назвать лучшим.

Вот это на полный балл

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 1000000

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int> > v(n + 2, vector<int>(m + 2, 0));
	vector<vector<int> > p(n + 2, vector<int>(m + 2, INF));

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> v[i][j];

	p[1][1] = 0;
	for (int k = 0; k < 5000; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				p[i][j] = min(p[i][j], p[i + 1][j] + (v[i + 1][j] != v[i][j]));
				p[i][j] = min(p[i][j], p[i - 1][j] + (v[i - 1][j] != v[i][j]));
				p[i][j] = min(p[i][j], p[i][j + 1] + (v[i][j + 1] != v[i][j]));
				p[i][j] = min(p[i][j], p[i][j - 1] + (v[i][j - 1] != v[i][j]));
			}

	cout << p[n][m];
	return 0;
}

Но оно мне не нравится.. Число 5к пришлось долго искать.. Да и само оно совсем не ахти..
Написал некий аналог bfs. Фишка в том, что bfs требует, чтобы первый найденный путь и был оптимальным, в нашем случае это ессесно не так..
Тогда я решил использовать кучу (aka очередь с приоритетом), чтобы хранить и быстро выбирать минимальный элемент (а он выбирается так : минимальный вес на текущий момент, если же у нас есть несколько элементов с минимальным весом, то я выбираю тот, у которого № волны меньше)

#include <iostream>
#include <queue>
#include <functional>

#define INF 1000000

using namespace std;

struct st
{
	int x, y, w, p;
	friend bool operator < (const st& a, const st& b);
};
bool operator < (const st& a, const st& b)
{
	if (a.w == b.w) return a.p < b.p;
	return a.w > b.w;
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int> > v(n + 2, vector<int>(m + 2)), p(n + 2, vector<int>(m + 2));

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> v[i][j];

	priority_queue<st, vector<st> > q;
	st t;
	t.x = 1; t.y = 1; t.w = 1; t.p = 0;
	vector<vector<int> > use(n + 2, vector<int>(m + 2, INF));
	q.push(t);
	use[1][1] = 1;
	while (!q.empty())
	{
		t = q.top(); q.pop();
		if (p[t.x][t.y] != 0 && p[t.x][t.y] < t.w) continue;
		p[t.x][t.y] = t.w;
		if (v[t.x - 1][t.y] != 0 && p[t.x - 1][t.y] == 0 && use[t.x - 1][t.y] > t.w + (v[t.x][t.y] != v[t.x - 1][t.y]))
		{
			st temp;
			temp.x = t.x - 1;
			temp.y = t.y;
			temp.w = t.w + (v[t.x][t.y] != v[temp.x][temp.y]);
			temp.p = t.p + 1;
			q.push(temp);
			use[t.x+1][t.y] = temp.w;
		}
		if (v[t.x + 1][t.y] != 0 && p[t.x + 1][t.y] == 0 && use[t.x + 1][t.y] > t.w + (v[t.x][t.y] != v[t.x + 1][t.y]))
		{
			st temp;
			temp.x = t.x + 1;
			temp.y = t.y;
			temp.w = t.w + (v[t.x][t.y] != v[temp.x][temp.y]);
			temp.p = t.p + 1;
			q.push(temp);
			use[t.x+1][t.y] = temp.w;
		}
		if (v[t.x][t.y - 1] != 0 && p[t.x][t.y - 1] == 0 && use[t.x][t.y - 1] > t.w + (v[t.x][t.y] != v[t.x][t.y - 1]))
		{
			st temp;
			temp.x = t.x;
			temp.y = t.y - 1;
			temp.w = t.w + (v[t.x][t.y] != v[temp.x][temp.y]);
			temp.p = t.p + 1;
			q.push(temp);
			use[t.x][t.y - 1] = temp.w;
		}
		if (v[t.x][t.y + 1] != 0 && p[t.x][t.y + 1] == 0 && use[t.x][t.y + 1]> t.w + (v[t.x][t.y] != v[t.x][t.y + 1]))
		{
			st temp;
			temp.x = t.x;
			temp.y = t.y + 1;
			temp.w = t.w + (v[t.x][t.y] != v[temp.x][temp.y]);
			temp.p = t.p + 1;
			q.push(temp);
			use[t.x][t.y + 1] = temp.w;
		}
	}

	cout << p[n][m] - 1;

	return 0;
}

Решение работает очень быстро, что сообственно я и хотел, но не всегда корректно..
Вот такой вот вердикт тестирующей системы

Время      Память  № первого проблемного теста  балл
10ms     512.00Kb    16	                          21

Когда первый вариант

	
0.597s   380.00Kb  - 25

UPDATE

Ах да, к сожалению, свой логин\пароль я потерял, и тестирую на сайте с аккаунта друзей.. Посему дать его Вам я не могу, уж пардоньте..
И еще.. Тестирующая система кушает код только на крестах и паскале (Free\Delphi)

[rrrFer]

Первый алгоритм оптимален. Лично я не вижу как этот АЛГОРИТМ можно оптимизировать, разве что эвристикой...
Я не понял откуда 5000 в примере, если это количество яблок - то должно быть 10000.

Мне кажется bfs тут неуместен.Или ты должен будешь запустить его 10 тысяч раз для разного количества яблок, но врядли это будет эффективнее.

[Poma][a]

Я не понял откуда 5000 в примере, если это количество яблок - то должно быть 10000.

Именно поэтому и не нравится..

for (int k = 0; k < 10000; k++)

Такой вариант дает TL на одном тесте

for (int k = 0; k < 1000; k++)

А такой WA на двух

Мне кажется bfs тут неуместен.Или ты должен будешь запустить его 10 тысяч раз для разного количества яблок, но врядли это будет эффективнее.

Не думаю..

[FPaul]

Я понимаю, что в 1-м алгоритме 10'000 было бы уместнее. А если добавить проверку на то, что во время очередной итерации по k путь (p[][]) не был улучшен и в таком случае прекратить поиск.
В поиске по алгоритмам на графах (e-maxx) увидел название "алгоритм Дейкстры за O (M log N)", который бы сюда подошёл. Но еще не успел с ним ознакомиться.

[Poma][a]

В поиске по алгоритмам на графах (e-maxx) увидел название "алгоритм Дейкстры за O (M log N)", который бы сюда подошёл.

Неа..
Нам просто не сделать такой граф

[FPaul]

А по поводу "добавить проверку на то, что во время очередной итерации по k путь (p[][]) не был улучшен и в таком случае прекратить поиск"?

[Poma][a]

Щас напишу
Все прошло! Пасиб

Но все равно не нравится..
Хочется чего-нить более оптимального..

[FPaul]

Оптимально - от [1,1] последовательно искать минимальные пути ко всем узлам графа. И на основе минимумов продвигаться к следующему узлу. Возможно, улучшая предыдущие оценки.

[Poma][a]

Если мы будет улучшать предыдущие оценки, то нужно будет все снова пересчитывать..