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

[FPaul]

Да. Пример - 1 программа. Но 5000, возможно, избыточно. Поэтому прекратить по условию невозможности улучшить.

[Poma][a]

Дык и получим первую
А хочется совершенно другой подход

[FPaul]

"алгоритм Дейкстры за O (M log N)" для разреженных матриц. Но судя по описанию e-maxx, реализация весьма непроста.

[Poma][a]

Реализация ни разу не сложнее bfs.. Правда для достижения логарифма придется использовать кучу..
И я ошибся.. Такой граф создать можно
Он будет состоять из n*m вершин..
Тогда для каждой вершины будет список ребер, причем длина этого списка находится в диапазоне [2;4]
Завтра напишу этот вариант..
Он, кстати, будет очень похож на мой нынешний (аля код#2)

[Poma][a]

Задачу я сдал..
Решил ради прикола глянуть свой код еще раз..
А там из-за копипасты косяк..
Вот так полный балл

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

#define INF 1000000

using namespace std;

struct st
{
	long long 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()
{
	long long n, m;
	cin >> n >> m;
	vector<vector<long long> > v(n + 2, vector<long long>(m + 2)), p(n + 2, vector<long long>(m + 2));

	for (long long i = 1; i <= n; i++)
		for (long long 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<long long> > use(n + 2, vector<long long>(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;
}

Всем спасибо!

Фактически я из bfs'а пришел к Дейкстре..
Ибо это он и есть.. Просто я не делаю список ребер, т.к. их кол-во меньше 5, я бахаю развилки


Для сравнения :
BFS

10ms 772.00Kb

1-ый вариант, выполняемый до тех пор, пока результат можно улучшить

414ms 380.00Kb

[rrrFer]

Я понимаю, что в 1-м алгоритме 10'000 было бы уместнее. А если добавить проверку на то, что во время очередной итерации по k путь (p[][]) не был улучшен и в таком случае прекратить поиск.

То программа будет работать неправильно. Результат может не улучшиться при k = 100, но улучшиться при k = 900, например. Представить себе такой пример весьма легко вроде бы. Поэтому надо перебирать все k от 1 до 10 тысяч.

[Poma][a]

То программа будет работать неправильно. Результат может не улучшиться при k = 100, но улучшиться при k = 900, например. Представить себе такой пример весьма легко вроде бы. Поэтому надо перебирать все k от 1 до 10 тысяч.

Не..
Разговор про то, что если p[i][j] (i = [1..n], j = [1..m]) не изменилось, то нужно закончить

[rrrFer]

Разговор про то, что если p[i][j] (i = [1..n], j = [1..m]) не изменилось, то нужно закончить

Это да, но это улучшить может оценку среднего случая, но не худшего. Т.е. я думаю что если программа на проходит по времени какой-то тест, то и с этой проверкой она тоже его не пройдет