Блуждание по Лабиринту

[Hrach_Techie]

...

[Hrach_Techie]

Dictionary of Algorithms and Data Structures
http://www.nist.gov/dads/

[Hrach_Techie]

....

#include <iostream>

#include <conio.h>

using namespace std;

static const int initX = 4;

static const int initY = 11;

static const int finalX = 2;

static const int finalY = 0;

static char maze[][12] =

{

'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#',

'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#',

'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#',

'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#',

'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.',

'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#',

'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#',

'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#',

'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#',

'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#',

'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#',

'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'

};

void printMaze();

int trav(int x, int y);

int main()

{

trav(initX, initY);
return 0;}

int trav(int x, int y)

{
printMaze();
getch();

if(x == finalX && y == finalY)
return 1;
const int arrX[] = {x, x + 1, x, x - 1};
const int arrY[] = {y + 1, y, y - 1, y};
for(int i = 0; i < sizeof(arrY) / sizeof(arrY[0]); i ++){

if(

arrX[i] == 12 ||

arrY[i] == 12 ||

maze[arrX[i]][arrY[i]] == '#' ||

maze[arrX[i]][arrY[i]] == 'X'
)

continue;

// cout << i << "," << arrX[i] << "," << arrY[i] << ":" << maze

//[arrX[i]][arrY[i]] << endl;
maze[arrX[i]][arrY[i]] = 'X';

if(trav(arrX[i], arrY[i]))

return 1;
}

return 0;

}

void printMaze()

{

for(int j = 0; j < 12; j ++)

{

for(int i = 0; i < 12; i ++){

cout << maze[j][i];

}

cout << endl;

}}

[nm]

поздеваюсь . ты сам себе работаешь черной кошкой и перебегаешь дорогу ))
дальше думай сам )))

насчет рекурсии ты правильно сообразил, но насчет реализации ее -- нет
пдф не смотрел

[u60311]

неверно решение в книге или точнее алгоритм он не оптимальный ... я бы разбил его иначе:

//***********************
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <string>
#include <iostream>
#include <ctime>
using namespace std;

class Maze
{
public:
Maze(int newSize);
virtual ~Maze();

void generate(int space_to_walls_ratio);
int* traverse(int &path_length);
string getMaze();
void print();
void trimLoops();
void printPath();

private:
int *maze, next[4], *start, *exit, size, side;
int *path, distance;

int* traverse(int *position, int direction, int &pathLength);

};

#endif // !defined(AFX_MAZE_H__4548599F_AF7C_4950_AF6E_1C5F1 59C4FCC__INCLUDED_)
//**************************
ну и далее вот так
// Maze.cpp: implementation of the Maze class.
//
//////////////////////////////////////////////////////////////////////

#include "Maze.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Maze::Maze(int newSize)
{
size = newSize;
maze = new int[size * size];
for (int i = 0; i < size * size; i++) maze[i] = 1;

next[0] = 1;
next[1] = size;
next[2] = -1;
next[3] = -size;

srand(time(0));
}

Maze::~Maze()
{
delete [] maze;
}

void Maze::generate(int space_to_walls_ratio)
{
int i, j, lastRow = size * (size - 1), hole;

for (i = 1; i < size - 1; i++)
for (j = 1; j < size - 1; j++)
maze[i * size + j] = 1 - (bool) (rand() % space_to_walls_ratio);

side = rand() % 4;
i = rand() % (size - 2) + 1;
switch (side) {
case 0:
hole = size * i;
break;
case 1:
hole = i;
break;
case 2:
hole = size * (i + 1) - 1;
break;
case 3:
hole = lastRow + i;
}

maze[hole] = maze[hole + next[side]] = 0;
exit = maze + hole;

side = rand() % 4, hole;
i = rand() % (size - 2) + 1;
switch (side) {
case 0:
hole = size * i;
break;
case 1:
hole = i;
break;
case 2:
hole = size * (i + 1) - 1;
break;
case 3:
hole = lastRow + i;
}

maze[hole] = maze[hole + next[side]] = 0;
start = maze + hole;
}

int* Maze::traverse(int *position, int direction, int &path_length)
{
int *result;
*position = 2;

if (position == start || position == exit) {
path_length = 1;
result = new int;
*result = position - maze;
return result;
}

int *path_tail;
if (*(position + next[(direction + 1) % 4]) != 1)
path_tail = traverse(position + next[(direction + 1) % 4], (direction + 1) % 4, path_length);
else if (*(position + next[direction]) != 1)
path_tail = traverse(position + next[direction], direction, path_length);
else
path_tail = traverse(position, (direction + 3) % 4, path_length);

result = new int[++path_length];
result[0] = position - maze;
for (int i = 0; i < path_length - 1; i++) result[i + 1] = path_tail[i];

delete [] path_tail;
return result;
}

int* Maze::traverse(int &path_length)
{
*start = 2;
int *tail = traverse(start + next[side], side, path_length);
int *result = new int[++path_length];
result[0] = start - maze;
for (int i = 0; i < path_length - 1; i++) result[i + 1] = tail[i];

delete [] tail;
return result;
}

string Maze::getMaze()
{
string result = "";
char symbols[3] = {'.', '#', 'o'};

for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++)
result += symbols[maze[i * size + j]];
result += "\n";
}

return result;
}

void Maze:rint()
{
cout << getMaze() << endl;
}

void Maze::trimLoops()
{
int *loops = traverse(distance), full_path = distance, step, previous_step, canceled_step;

for (step = 0; step < full_path; step++)
for (previous_step = step - 1; previous_step >= 0; previous_step--)
if (loops[previous_step] == loops[step])
for (canceled_step = previous_step; canceled_step < step; canceled_step++)
loops[canceled_step] = -1;

path = new int[distance];
step = 0;
for (canceled_step = 0; canceled_step < full_path; canceled_step++)
if (loops[canceled_step] != -1) {
path[step] = loops[canceled_step];
step++;
}
else
distance--;

delete [] loops;
}

void Maze:rintPath()
{
trimLoops();
for (int i = 0; i < distance; i++)
cout << path[i] << " ";
cout << endl;
}
ну а дальше ещё проще
//************************************
#include "Maze.h"

void main()
{
int length, *path;
Maze obj(10);
obj.generate(3);
obj.print();
path = obj.traverse(length);
obj.print();
for (int i = 0; i < length; i++)
cout << path[i] << " ";
cout << endl;
obj.printPath();
}
//**********************************

сойдёт?