Поиск всех путей в лабиринте от точки до точки

[pavel_abelardo]

Товарисчи. Занимаюсь поиском всех путей в лабиринте от точки до точки. Количество путей определить удалось. А вот координаты точек путей установить не удалось. Вот в этом загвозка момогите, а. Проблема именно в функции find_path(x,y). Так как используется рекурсия и с внутренними условиями, то не удаётся установить конкретные координаты пути. Помогите очень надо((((

#include <iostream>
#include <string>
#include <string.h>
#include <conio.h>
using namespace std;


#define FALSE 0
#define TRUE 1

#define NROWS 5
#define MCOLS 5

// Symbols:
// '.' = open
// '#' = blocked
// '+' = path

char maze[NROWS][MCOLS] = {
		{'#','#','.','.','.'},
		{'#','#','.','.','.'},
		{'#','#','.','.','.'},
		{'#','#','#','#','#'},
		{'#','#','#','#','#'}
};


void display_maze(void);
int find_path(int x, int y);

int main(void)
{
		display_maze();

		if ( find_path(2, 0) == TRUE )
				printf("Success!\n");
		else
				printf("Failed\n");

		display_maze();
		int i;
		cin >> i;
		return 0;
}

void
display_maze(void)
{
		int i;
		printf("MAZE:\n");
		for ( i = 0; i < NROWS; i++ )
				printf("%.*s\n", MCOLS, maze[i]);
		printf("\n");

		return;
}




unsigned short int *ok=new unsigned short int[82000],upper=0;
int find_path(int x, int y)
{

		// If x,y is outside maze, return false.
		if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return FALSE;
		// If x,y is the goal, return true.
		if ( x==4 && y == 2 ){
			l = 1;
			cout<<x<<"!:!"<<y<<"   ::"<<l<<" -0"<<endl;
			p++;
			return TRUE;

		}
		// If x,y is not open, return false.
		if ( maze[y][x] != '.') return FALSE;

		_1 = 0;
		_2 = 0;
		_3 = 0;
		_4 = 0;

		// Mark x,y part of solution path.
		maze[y][x] = '+';
		up++;
		ok[up] = 0;
		// If find_path North of x,y is true, return true.
		if ( find_path(x, y - 1) == TRUE ){
			//maze[y][x]='.';
			_1 = y-1+10*x;
			cout<<x<<":"<<y<<"   ::"<<++l<<" -2"<<endl;
			ok[up] =1;
			//return TRUE;
		}

		// If find_path East of x,y is true, return true.
		if ( find_path(x + 1, y) == TRUE ){
			//maze[y][x]='.';
			if(_1 != 0) cout<<"-------- 4 -- "<<_1<<endl;
			_2 = y+10*(x+1);
			cout<<x<<":"<<y<<"   ::"<<++l<<" -3"<<endl;
			ok[up] =1;
			//return TRUE;
		}

		// If find_path South of x,y is true, return true.
		if ( find_path(x, y + 1) == TRUE ) {
			//maze[y][x]='.';
			if(_1 != 0 ) cout<<"-------- 3 -- "<<_1<<endl;
			if(_2 != 0) cout<<"-------- 3 -- "<<_2<<endl;
			_3 = y+1+10*x;
			cout<<x<<":"<<y<<"   ::"<<++l<<" -4"<<endl;
			ok[up] =1;
			//return TRUE;
		}

		// If find_path West of x,y is true, return true.
		if ( find_path(x - 1, y) == TRUE ) {
			//maze[y][x]='.';
			if(_1 != 0 ) cout<<"-------- 2 -- "<<_1<<endl;
			if(_2 != 0) cout<<"-------- 2 -- "<<_2<<endl;
			if(_3 != 0) cout<<"-------- 2 -- "<<_3<<endl;
			_4 = y+1+10*x;

			cout<<x<<":"<<y<<"   ::"<<++l<<" -5"<<endl;
			ok[up] = 1;
			//return TRUE;
		}

		// Unmark x,y as part of solution path.
		maze[y][x]='.';

		if(ok[up]) {

			return TRUE;
		}

		return FALSE;
}

[pavel_abelardo]

Помогите правильно вывести координаты пути.

[pavel_abelardo]

Что же никто не может помочь мне?

[Jakethefish]

На первый взгляд есть небольшая путаница с файнд паф. У Вас соут проходит? Как работает ваша программа? Пробовали ли делать дебаг?


http://www.delphikingdom.com/asp/vie...?catalogID=166
В вашем случае препятствие - непроходимая точка лабиринта.

[pavel_abelardo]

Она ищет все возможные пути от (2,0) до (4,2). Как ищется рекурсивно. как только точка оказывается (4,2) начинаются возвращаться координаты, с помощью вывода на экран. Но так как при каждом рекурсивном вызове функции поиска пути идёт разветвление на 4 части. и поэтому выводится куча значений. а не определённые пути. Что я тока не пробовал(((

[pavel_abelardo]

Может здесь рекурсия не подойдёт, а тогда как?

[Jakethefish]

Немного непонятно зачем вам

		_1 = 0;
		_2 = 0;
		_3 = 0;
		_4 = 0;

Лабиринт мы проходили при помощи метода клубок ниток.
Суть метода такова: если я куда-то иду, то клубок разматывается, если я пришел в тупик, то сматываю клубок.
То есть в каком то массиве содержатся все пройденные комнаты. Вероятно вы можете создать пустую копию вашего лабиринта, двойной массив, в который вы будете записывать то куда шли, либо в него записывать только правильный путь, то есть перед return true. Это видимо вам и так известно.

Получается ваша проблема в том, чтобы отобразить несколько путей, а не 1?
Возможно тогда стоит попробовать что-то вроде такого:
0000
0001
0010
0011
и тд.
Прям как задача по тер. веру. А что будет если я 4 раза пойду на север? 3 раза на север 1 раз на восток, 3 раза на север 1 раз на запад, 3 раза на север 1 раз на юг?
Только у вас не 4 раза а предположим 100 раз.
Реализуем циклами.
Основная проблема - как не петлять. Решение - записываем куда мы уже ходили.
Как-то так. Советую попробовать на лабиринте 2х2, и дальше уже увеличивать размер.
Если вы будете соблюдать порядок, то сможете разматывать и сматывать "клубок", пока не упретесь в тупик либо пока не упретесь в "нитку".

Хотя возможно есть и более лучшие варианты.

[pavel_abelardo]

               _1 = 0;
		_2 = 0;
		_3 = 0;
		_4 = 0;

Этим я пытался уловить разветвления. И установить системность записи координат.

[pavel_abelardo]

Да я хочу отобразить все возможные пути. Дело в том что если в каждом условии сделать "return true" то тогда он найдёт тока один первый построенный путь. а если в конце проверять что хоть одно условие выполнилось:

if(ok[up]) {

			return TRUE;
		}

То получается белеберда. но определяется точное кол-во путей. Но вот то что разветвление он выводит координаты не по целым веткам, а кусочно.

4!:!2
4:1
4!:!2
3:2
4!:!2
3:2
2:2
2:1
3:1
4:1
4:0
3:0
4!:!2
4:1
3:1
4!:!2
3:2
4!:!2
3:2
2:2
2:1
3:1
3:0
2:0
4!:!2
4:1
4:0
3:0
3:1
4!:!2
4:1
3:1
4!:!2
3:2
4!:!2
4:1
4:0
3:0
3:1
4!:!2
4:1
3:1
3:2
4!:!2
3:2
2:2
2:1
2:0

Здесь видно что как только выполняется другая ветка он её печатает до следующей найденной ветке.
В моей программе переписывается каждая пройденная свободная точка в "+" чтобы не пройти ещё раз её.
А что значит :

Возможно тогда стоит попробовать что-то вроде такого:
0000
0001
0010
0011
и тд.

я хоть и сегодня тер вер на 5 сдал. но чё то не понял((

[Jakethefish]

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

Да, вероятно слишком трудно объяснил.
Мой способ не идеален, думаю есть что-то и лучше. Вы идете на север, упираетесь в стену, шаг назад, идете к примеру на восток шаг, и снова на север, если уперлись, то снова направо шаг, и снова на север, если упремся при повороте на юг, нужно вернуться и идти на юг. Хотя сейчас смотрю, и как-то не очень алгоритм.

Кстати вероятно вариант с копией лабиринта самый лучший.
То есть у вас есть функция print_maze к примеру. Когда у вас выполняется условие:

		// If x,y is the goal, return true.
		if ( x==4 && y == 2 ){
			l = 1;
			cout<<x<<"!:!"<<y<<"   ::"<<l<<" -0"<<endl;
			p++;
			return TRUE;

		}

Вместо

cout<<x<<"!:!"<<y<<"   ::"<<l<<" -0"<<endl;

вы делаете print_maze(). В функции выписывается текущее состояние лабиринта к примеру.
Либо у вас есть какой-то массив\вектор который содержит текущий путь. Когда приходим к точке, то печатаем данный массив. Если мы ищем путь дальше, то есть делаем шаг назад и образуем ветвление, нужно удалить последний элемент массива пути. В принципе можно создать какую-то структуру типа linked list, и либо удалять либо добавлять в неё элементы.