@OneArt

Создал программу, которая генерирует лабиринт из двумерного массива, где 0 - стенки лабиринта, 1 - проходы, 2 - начало, 3 - конец, 4 - путь. Генерация происходит от введенных пользователем данных. Было решено найти выход рекурсивным методом, за основу было взято решение отсюда. Не знаю уже в чем проблема, мозг не варит.

Собственно сам код:

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<windows.h>
using namespace std;

bool deadend(int, int, int**, int, int);//Генерация тупиков в лабиринте
void visual(int**, int, int);//Визуализация лабиринта
int mazemake(int**, int, int);//Генерация лабиринта
bool Solve(int**,int, int, int, int, int, int);//Решение
const int wall = 0, pass = 1, start = 2, finish = 3, path = 4;


bool ended(int** maze, int height, int width){ //Проверка генерации лабиринтов
bool b = 1;

for(int i = 1; i < (height - 1); i += 2)
for(int j = 1; j < (width - 1); j += 2)
if(maze[i][j] == wall)
b = 0;
return b;
}

int main(){

SetConsoleCP(1251);
SetConsoleOutputCP(1251);
setlocale(LC_ALL, "Russian");

int height, width, beginx, endx, beginy, endy;


cout<<"Введите высоту лабиринта (нечетное число): "<<endl;
while(true){
cin>>height;
if (!cin ||height<0 ||height>55||height%2==0)
{
cout<<"Ошибка! Попробуйте еще раз!" <<endl;
cin.clear();
while(cin.get()!='\n');
}
if(cin.get()!='\n')
{
cout<<"Подтвердите корректность: "<<endl;
cin.clear();
while(cin.get()!='\n');
}
else
break;
}
cout<<"Введите ширину лабиринта (нечетное число): "<<endl;

while(true){
cin>>width;
if (!cin ||width<0 ||width>55||width%2==0)
{
cout<<"Ошибка! Попробуйте еще раз!" <<endl;
cin.clear();
while(cin.get()!='\n');
}
if(cin.get()!='\n')
{
cout<<"Подтвердите корректность: "<<endl;
cin.clear();
while(cin.get()!='\n');
}
else
break;
}

cout<<"Висота: "<<height<<endl;
cout<<"Ширина: "<<width<<endl;

beginx=0;
beginy=height-2;
endx=width-1;
endy=1;

//Выделение памяти
int** maze = new int*[height];
for(int i = 0; i < height; i++)
maze[i] = new int[width];

//Генерация лабиринта
mazemake(maze, height, width);
visual(maze,height,width);

//Решение
if(Solve(maze,beginx,beginy,endx,endy,height,width)) //Ошибка где-то в этой функции
{
visual(maze,height,width);
}
else
{
cout<<"Не удалось найти выход!"<<endl;
};



//Очищение помяти
for(int i = 0; i < height; i++)
delete[] maze[i];
delete[] maze;

return 0;
}

bool deadend(int x, int y, int** maze, int height, int width){
int a = 0;

if(x != 1){
if(maze[y][x-2] == pass)
a+=1;
}
else a+=1;

if(y != 1){
if(maze[y-2][x] == pass)
a+=1;
}
else a+=1;

if(x != width-2){
if(maze[y][x+2] == pass)
a+=1;
}
else a+=1;

if(y != height-2){
if(maze[y+2][x] == pass)
a+=1;
}
else a+=1;

if(a == 4)
return 1;
else
return 0;
}

void visual(int** maze, int height, int width){
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++)
switch(maze[i][j]){
case wall: cout<<"[]"; break;
case pass: cout<<" "; break;
case start: cout<<" "; break;
case finish: cout<<" "; break;
case path: cout<<"* "; break;
}
cout<<endl;
}
cout<<endl;
}

int mazemake(int** maze, int height, int width){
int x, y, c, a;
bool b;

for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
maze[i][j] = wall;

x = 5; y = 5; a = 0;
while(true){
a++;
if(a%100 == 0)
if(ended(maze, height, width))
break;
maze[y][x] = pass;

while(true){
c = rand()%4;
switch(c){
case 0: if(y != 1)
if(maze[y-2][x] == wall){
maze[y-1][x] = pass;
maze[y-2][x] = pass;
y-=2;
}
case 1: if(y != height-2)
if(maze[y+2][x] == wall){
maze[y+1][x] = pass;
maze[y+2][x] = pass;
y+=2;
}
case 2: if(x != 1)
if(maze[y][x-2] == wall){
maze[y][x-1] = pass;
maze[y][x-2] = pass;
x-=2;
}
case 3: if(x != width-2)
if(maze[y][x+2] == wall){
maze[y][x+1] = pass;
maze[y][x+2] = pass;
x+=2;
}
}
if(deadend(x,y,maze,height,width))
break;
}

if(deadend(x,y,maze,height,width))
do{
x = 2*(rand()%((width-1)/2))+1;
y = 2*(rand()%((height-1)/2))+1;
}
while(maze[y][x] != pass);
}
maze[height-2][0] = start;
maze[1][width-1] = finish;
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
return maze[i][j];
}

bool Solve(int **maze,int beginx, int beginy, int endx, int endy, int height, int width){

//Делаем ход, помечая элемент массива как "найденный путь"
maze[beginy][beginx] = path;

// Проверяем найден ли выход
if (beginx == endx && beginy == endy)
{
return true;
}

// Рекурсивный поиск выхода
if (beginx > 0 && maze[beginy][beginx - 1] == pass && Solve(maze,beginx - 1,beginy,endx,endy,height,width))
{
return true;
}
if (beginx < width && maze[beginy][beginx + 1] == pass && Solve(maze,beginx + 1,beginy,endx,endy,height,width))
{
return true;
}
if (beginx > 0 && maze[beginy - 1][beginx] == pass && Solve(maze,beginx, beginy - 1,endx,endy,height,width))
{
return true;
}
if (beginy < height && maze[beginy + 1][beginx] == pass && Solve(maze,beginx, beginy + 1,endx,endy,height,width))
{
return true;
}

// В противном случае, возвращаемся к прошлому найденному пути и ищем другое решение
maze[beginy][beginx] = pass;

return false;
};

Добавлено через 18 минут
Как бы я не пытался, программа , а точнее функция Solve(), не хочет находить решение.

0