Прохождение лабиринта (волновой алгоритм) - Общие вопросы C/C++

Alexander_A · 27.10.2011, 20:55

Добрый день.
Решаю задачу №129 с сайта acm.mipt.ru.

http://acm.mipt.ru/judge/problems.pl...2a362a981a81c7

Для тех, кто не знает: это сайт с автоматической проверкой написанных программ с помощью некоторого количества тестов (версия компилятора С++ 3.4.6).
По сути дела, задача сводится к написанию программы для прохождения лабиринта. На входе указывается его размерность, количество и координаты препятствий, а также стартовая и конечная позиции. На выходе программа выдает длину пути и его описание.

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

Код:

#include "stdafx.h"
#include "conio.h"


int XS, YS, XE, YE;

int X, Y, I;

int Moves; // Длина пути

int i, j, l, P;

int N, M, K; // N - количество столбцов 
			 // M - количество строк
			 // K - количество проводов

int Xn, Yn, Xk, Yk; // Координаты начала и конца проводов

int a=0, b=0, c=0, d=0;




int main()
{
	scanf("%d %d %d\n", &N, &M, &K); // Ввод размерности леса и числа проводов


	int **Map = new int *[M*2+1]; // Массив для сохранения карты леса
	for(i=0; i<=(M*2); i++)
		Map[i] = new int [N*2+1];

	int **MapM = new int *[M*2+1]; //Массив для волнового алгоритма
	for(i=0; i<=(M*2); i++)
		MapM[i] = new int [N*2+1];


	for(i=0; i<=(M*2); i++)
		for(j=0; j<=(N*2); j++)
		{
			if(((i%2) != 0) && ((j%2) != 0))
				Map[i][j] = 1;
			else
				Map[i][j] = 0;
			MapM[i][j] = 0;
		}


	scanf("%d %d %d %d\n", &XS, &YS, &XE, &YE); // Ввод координат точек А и В

	if((XS > N) || (YS > M) || (XE > N) || (YE > M))
	{
		printf("NO SOLUTION");
		getch(); ///////////////////////
		return 0; //ostanovka programmi
	}


	for(l=1; l<=K; l++)
	{
		scanf("%d %d %d %d\n", &Xn, &Yn, &Xk, &Yk); // Ввод координат начала и конца проводов

		if((Xn > N) || (Yn > M) || (Xk > N) || (Yk > M))
		{
			printf("NO SOLUTION");
			getch(); ///////////////////////
			return 0; //ostanovka programmi
		}


		if(Xn == Xk) // Проверяем паралельность провода оси OY
		{
			if(Yn > Yk) // Если переменная Yn > Yk, то меняем их местами
			{
				P = Yn;
				Yn = Yk;
				Yk = P;
			}

			for(i=(Yn*2); i<=(Yk*2); i++) // Наносим провод на карту
				Map[i][Xn*2] = 1;
		}

		if(Yn == Yk) // Аналогично для OX
		{
			if(Xn > Xk)
			{
				P = Xn;
				Xn = Xk;
				Xk = P;
			}

			for(i=(Xn*2); i<=(Xk*2); i++)
				Map[Yn*2][i] = 1;
		}


		if((Xn != Xk) && (Yn != Yk)) // Для проводов, не паралельных координатным осям
		{
			int ch, zn, b;

			ch = Yn - Yk;			// Находим числитель
			zn = Xn - Xk;			// и знаменатель коэффициента К,
			b = Yk - ch*Xk/zn;		// а также коэффициэнт В

			if(Xn > Xk)
			{
				P = Xn;
				Xn = Xk;
				Xk = P;
			}

			if(Yn > Yk)
			{
				P = Yn;
				Yn = Yk;
				Yk = P;
			}

			for(i=Xn; i<=Xk; i++)			// Находим точки пересечения отрезка с прямыми X = B
			{								// и наносим их на карту
				if(((ch*i)%zn) == 0)
					Map[((ch*i)/zn+b)*2][i*2] = 1;
				else
					for(j=0; j<M; j++)
						if((((float)(ch*i)/(float)zn+b) > j) && (((float)(ch*i)/(float)zn+b) < (j+1)))
						{
							Map[j*2+1][i*2] = 1;
							break;
						}
			}

			for(i=Yn; i<=Yk; i++)			// Аналогично для прямых Y = B
			{
				if((((i-b)*zn)%ch) == 0)
					Map[i*2][(((i-b)*zn)/ch)*2] = 1;
				else
					for(j=0; j<N; j++)
						if((((float)((i-b)*zn)/(float)ch) > j) && (((float)((i-b)*zn)/(float)ch) < (j+1)))
						{
							Map[i*2][j*2+1] = 1;
							break;
						}
			}


		}


	}

Alexander_A · 27.10.2011, 20:57

Продолжение кода.

Код:

	XS = XS*2;
	YS = YS*2;
	XE = XE*2;
	YE = YE*2;




	if((Map[YS][XS] == 1) || (Map[YE][XE] == 1))
	{
		printf("NO SOLUTION");
		getch(); ///////////////////////
		return 0; //ostanovka programmi
	}

	MapM[YS][XS] = 1;
	I = 1;

	do				// Заполняем массив MapM[][] числами, показывающими длину пути
	{				// до данной точки
		I++;

		for(Y=0; Y<=(M*2); Y++)
			for(X=0; X<=(N*2); X++)
				if(MapM[Y][X] == (I-1))
				{
					if((Y < M*2) && (MapM[Y+1][X] == 0) && (Map[Y+1][X] == 0))
						MapM[Y+1][X] = I;

					if((Y > 0) && (MapM[Y-1][X] == 0) && (Map[Y-1][X] == 0))
						MapM[Y-1][X] = I;

					if((X < N*2) && (MapM[Y][X+1] == 0) && (Map[Y][X+1] == 0))
						MapM[Y][X+1] = I;

					if((X > 0) && (MapM[Y][X-1] == 0) && (Map[Y][X-1] == 0))
						MapM[Y][X-1] = I;
				};

		if(I == N*M*4)
		{
			printf("NO SOLUTION");
			getch(); ///////////////////////
			return 0; //ostanovka programmi
		}

	}
	while(MapM[YE][XE] <= 0);

	Moves = I - 2;
	X = XE;
	Y = YE;
	Map[YE][XE] = 4;

	printf("%d\n", (Moves+1)/2); // Вывод длины пути

	int *Put = new int [I+1];	 // Объявляем массив Put[] для сохранения
								 // направления движения
	for(I = Moves; ; I--)		 // Отмечаем путь в массиве Map[][] и заполняем массив Put[]
	{

		if((X < N*2) && (MapM[Y][X] - MapM[Y][X+1] == 1))
		{
			X++;
			a++;
			if(a == 2)
			{
				Put[I] = 1;
				a=0;
			}
		}
		else
		{
			if((X > 0) && (MapM[Y][X] - MapM[Y][X-1] == 1))
			{
				X--;
				b++;
				if(b == 2)
				{
					Put[I] = 2;
					b=0;
				}
			}
			else
			{
				if((Y < M*2) && (MapM[Y][X] - MapM[Y+1][X] == 1))
				{
					Y++;
					c++;
					if(c == 2)
					{
						Put[I] = 3;
						c=0;
					}
				}
				else
				{
					if((Y > 0) && (MapM[Y][X] - MapM[Y-1][X] == 1))
					{
						Y--;
						d++;
						if(d == 2)
						{
							Put[I] = 4;
							d=0;
						}
					}
				}
			}
		}

			

		Map[Y][X] = 3;
		if((X == XS) && (Y == YS)) break;
	}

	for(I=0; I<=(Moves-1); I++) // Печать описания пути
	{
		switch(Put[I])
		{
			case 1:
				printf("W");
				break;

			case 2:
				printf("E");
				break;

			case 3:
				printf("S");
				break;

			case 4:
				printf("N");
				break;
		}
	}

	Map[YS][XS] = 2;

//-----------------------------------
/**/
// Печать массива
	getch();

	printf("\n\n");

	for(i=(M*2); i>=0; i--)
	{
		if(i/10 == 0) printf("%d  ", i);
		else printf("%d ", i);
		for(j=0; j<=(N*2); j++)
		{
			if(i == YS && j == XS) printf("S ");
			else
			{
				if(i == YE && j == XE) printf("F ");
				else
				{
					if(((i%2) != 0) && ((j%2) != 0))
						printf("# ");
					else
						printf("%d ", Map[i][j]);
				}
			}
			
		}	
		printf("\n");
	}

	printf("\n");
	printf("   ");

	for(j=0; j<=(N*2); j++)
	{
		if(j/10 == 0) printf("%d ", j);
		else printf("%d", j);
	}

	printf("\n");

	getch();


//-----------------------------------

	return 0;

}

В принципе, программа вполне работоспособна. Но при проверке на сайте она не может пройти пятый проверочный тест. К сожалению, разработчики сайта открыто их не публикуют.

Подскажите, где может быть ошибка.

P.S.:
Буду рад, если кто-нибудь сможет предложить нестандартные примеры для тестирования моей программы. Тесты принимаются как в формате входных данных (как в примере на сайте), так и в форме рисунка лабиринта (прямоугольного леса).
Жду ваших предложений и интересных тестов. Заранее, спасибо за ответы.

Abstraction · 27.10.2011, 21:36

1) Вы бы хоть на подпрограммы разбили. От такой простыни натурально дурно.
2) На каждом шаге волны перебирать наново весь массив - это крутой подход. Рискуете на очередном тесте не уложиться по времени. Вообще, причина провала на пятом тесте - "неверный ответ"?
3) Я так понимаю, что последний блок - это тестовая печать, которой нет в сдаваемой программе?
4) Из условия непонятно, можно ли проходить по краю леса (т.е. через узлы вида (0,3)). Пробовали разрешать это программе?

Alexander_A · 27.10.2011, 22:03

Цитата:

Сообщение от Abstraction

1) Вы бы хоть на подпрограммы разбили. От такой простыни натурально дурно.

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

Цитата:

Сообщение от Abstraction

2) На каждом шаге волны перебирать наново весь массив - это крутой подход. Рискуете на очередном тесте не уложиться по времени. Вообще, причина провала на пятом тесте - "неверный ответ"?

В данном случае время работы не столь важно. Time limit = 2 секунды, а программа работает намного быстрее.
А причину провала вы правильно определили.

Цитата:

Сообщение от Abstraction

3) Я так понимаю, что последний блок - это тестовая печать, которой нет в сдаваемой программе?

Тоже верно.

Цитата:

Сообщение от Abstraction

4) Из условия непонятно, можно ли проходить по краю леса (т.е. через узлы вида (0,3)). Пробовали разрешать это программе?

Думаю можно, программа успешно с этим справляется. Хотя стоит попробывать временно убрать эту возможность.

"По крайним просекам преступник также может перемещаться".
Вообще, эту фразу можно трактовать по-разному. В зависимости от того, что считать просекой.

Abstraction · 27.10.2011, 22:17

Цитата:

Сообщение от Alexander_A

"По крайним просекам преступник также может перемещаться".
Вообще, эту фразу можно трактовать по-разному. В зависимости от того, что считать просекой.

Убиться веником. Я открываю ссылку, вижу условие на английском, и мне даже в голову не приходит, что есть дубль на русском, более того - с новыми подробностями. В английском варианте нет даже намёка на эту фразу.

Тогда отдельно обращаю внимание, что в нынешнем варианте все координаты жёстко больше нуля.

L6go1as · 27.10.2011, 22:23

Чувствую себя ****мом, если сравнить задачи те, что я пытаюсь решить и эти ...
Ох ...

Alexander_A · 28.10.2011, 18:58

Цитата:

Сообщение от Abstraction

Тогда отдельно обращаю внимание, что в нынешнем варианте все координаты жёстко больше нуля.

В том смысле, что преступник не может передвигаться по краю леса? (например, от точки (0,0) до точки (2,0)) Я правильно вас понял?

После того как я отредактировал код, убрав возможность передвижения по периметру леса, программа стала выдавать неверный ответ на четвертом тесте. Замечу, что в примере с сайта провода начинаются на краю леса. Т. е. преступник теоретически мог там пройти.

Думаю, что проблема в чем-то другом.

Abstraction · 28.10.2011, 21:20

Цитата:

Сообщение от Alexander_A

После того как я отредактировал код, убрав возможность передвижения по периметру леса, программа стала выдавать неверный ответ на четвертом тесте. Замечу, что в примере с сайта провода начинаются на краю леса. Т. е. преступник теоретически мог там пройти.

Нет, проводов-барьеров даже касаться нельзя, если судить по второму тестовому примеру (если бы их можно было касаться, путь бы существовал).
И что значит - "убрав"? В приведённом здесь варианте программа, насколько могу видеть, не пытается вести волну через клетки с одной из координат ноль, соответственно, на карте

Код:

программа выдаст "нет пути", а между тем путь WWWNNNNEEES приводит к цели.
Или я ошибаюсь?

Alexander_A · 28.10.2011, 21:37

Цитата:

Сообщение от Abstraction

Код:

программа выдаст "нет пути", а между тем путь WWWNNNNEEES приводит к цели.
Или я ошибаюсь?

Отчасти. Да, в этом примере он приведет к цели.
Но у вас в четвертой строке ошибка, в примере на сайте строка начинается с 0, а не с 2.

Код:

А под словом «убрав» я имел в виду запрет на передвижение по координатным осям, а также по прямым X=N и Y=M (хотя это уже и так понятно).

Alexander_A · 30.10.2011, 19:52

После долгих поисков я наконец-то нашел ошибку. Оказалось, что проблема была в той части программы, которая наносит провода на карту. Я не учел то, что коэффициент «В» уравнения «У = К*Х + В» может быть нецелым числом.

Теперь программа работает без ошибок.
Спасибо Abstraction за уделенное внимание.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Надо поправить код.(Волновой алгоритм, Pascal)	DoubleTrouble	Помощь студентам	1	26.06.2011 18:23
Волновой алгоритм сферическая волна	ArtInt	Общие вопросы Delphi	2	24.04.2010 15:43
Алгоритм прохождения лабиринта	PAVEL315	Общие вопросы Delphi	13	02.01.2010 01:22
Волновой алгоритм поиска	Merkator	Gamedev - cоздание игр: Unity, OpenGL, DirectX	8	12.02.2009 16:15
Прохождение подземного лабиринта Джаффара	МаксимNEWProgramm	Паскаль, Turbo Pascal, PascalABC.NET	3	12.04.2008 19:52

27.10.2011, 21:36	#3
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	1) Вы бы хоть на подпрограммы разбили. От такой простыни натурально дурно. 2) На каждом шаге волны перебирать наново весь массив - это крутой подход. Рискуете на очередном тесте не уложиться по времени. Вообще, причина провала на пятом тесте - "неверный ответ"? 3) Я так понимаю, что последний блок - это тестовая печать, которой нет в сдаваемой программе? 4) Из условия непонятно, можно ли проходить по краю леса (т.е. через узлы вида (0,3)). Пробовали разрешать это программе?

27.10.2011, 22:23	#6
L6go1as Форумчанин Регистрация: 20.10.2011 Сообщений: 433	Чувствую себя ****мом, если сравнить задачи те, что я пытаюсь решить и эти ... Ох ...

30.10.2011, 19:52	#10
Alexander_A Пользователь Регистрация: 27.10.2011 Сообщений: 13	После долгих поисков я наконец-то нашел ошибку. Оказалось, что проблема была в той части программы, которая наносит провода на карту. Я не учел то, что коэффициент «В» уравнения «У = К*Х + В» может быть нецелым числом. Теперь программа работает без ошибок. Спасибо Abstraction за уделенное внимание.