Моя реализация волнового алгоритма Ли.
Лабиринт хранится в файле in.txt. (# - стена; S - старт; G - финиш; свободный сектор - точка или пробел)
В результате: в командную строку выводится количество шагов
в файл out.txt выводится лабиринт и все кратчайшие пути
Лабиринт хранится в файле in.txt. (# - стена; S - старт; G - финиш; свободный сектор - точка или пробел)
В результате: в командную строку выводится количество шагов
в файл out.txt выводится лабиринт и все кратчайшие пути
/*
Входной файл: in.txt
Выходной файл: out.txt
Условные обозначения во входном и выходном файлах:
'.' = доступная позиция
'#' = стена
'S' = старт
'G' = финиш
'+' = путь
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
#include <windows.h>
#include <stdio.h>
#define FALSE 0
#define TRUE 1
//максимальный размер лабиринта
#define MAX_NROWS 80
#define MAX_MCOLS 160
int nRows=0;
int mCols=0;
char maze[MAX_NROWS][MAX_MCOLS]={'#'}; //матрица-лабиринт
int steps[MAX_NROWS][MAX_MCOLS]={0};//матрица расстояний от старта
//до всех возможных точек
int find_min_path(int x,int y);
int find_path(int x, int y,int step);
//функция загрузки лабиринта из файла в массив
int load() {
FILE *f;
if ((f = fopen("in.txt","r"))==NULL)
return FALSE;
char ch;
int i=0,j=0;
do {
do {
ch = fgetc(f);
if (ch==' ') //пробелы заменяем на точки
ch='.';
maze[i][j]=ch;
if (i>MAX_NROWS || j>MAX_MCOLS)
return FALSE;
if (j>mCols)
mCols=j;
j++;
} while (ch!='\n' && ch!=EOF);
j=0;
i++;
if (i>nRows )
nRows=i;
} while (!feof(f));
fclose(f);
return TRUE;
}
// функция сохранения результата в файл
//(лабиринт со всеми кратчайшими путями)
int save() {
FILE *f;
f = fopen("out.txt","a+");
for (int i = 0; i <nRows;i++ )
{
for (int j = 0; j <mCols;j++ )
{
fputc(maze[i][j],f);
}
fputc('\n',f);
}
fputs("\n\n",f);
fclose(f);
}
//функция нахождения произвольного символа в лабиринте
//(для нахождения координат старта и финиша)
void findSymbol(int &x,int &y,char Symbol) {
for (int i = 0; i <nRows;i++ )
{
for (int j = 0; j <mCols;j++ )
{
if (maze[i][j]==Symbol){
x=i;
y=j;
return;
}
}
}
}
int num = 0; //минимальное количество шагов
int main(void)
{
load();
int x=0,y=0;
findSymbol(x,y,'S');
find_path(y, x,0);
findSymbol(x,y,'G');
find_min_path(y,x);
printf("Success!\n");
save();
printf("Steps: %i\n",num);
getch();
return 0;
}
//рекурсивная функция заполнения матрицы расстояний
int find_path(int x, int y,int step)
{
//если вышли за пределы лабиринта - возвращаемся
if ( x < 0 || x > mCols - 1 || y < 0 || y > nRows - 1 ) return FALSE;
//если дошли до финиша - возвращаемся
if ( maze[y][x] == 'G' ) return FALSE;
//если наткнулись на стену - возвращаемся
if (maze[y][x] == '#') return FALSE;
//если путь свободен - увеличиваем количество шагов
//и запоминаем его в мацциве
if (maze[y][x]!='S' && maze[y][x]!='G') {
step++;
if (steps[y][x]>step || steps[y][x]==0)
{
steps[y][x]=step;
}
}
//4 напровления - 4 вызова
//идем в определенном направлении если мы там еще не были
//(расстояние м матрице расстояний==0)
//или соблюдаются все условия:
//1) расстояние там больше текущего+1
//2) расстояние там не рамно текущее-1
//(что бы не пойти обратно тому же пути)
if (maze[y][x+1]!='S')
if ((steps[y][x+1]>(step+1) && steps[y][x+1]!=(step-1)) || steps[y][x+1]==0)
if ( find_path(x + 1, y,step) == TRUE ) return FALSE;
if (maze[y][x-1]!='S')
if ((steps[y][x-1]>(step+1) && steps[y][x-1]!=(step-1) ) || steps[y][x-1]==0)
if ( find_path(x - 1, y,step) == TRUE ) return FALSE;
if (maze[y+1][x]!='S')
if ((steps[y+1][x]>(step+1) && steps[y+1][x]!=(step-1) ) || steps[y+1][x]==0)
if ( find_path(x, y + 1,step) == TRUE ) return FALSE;
if (maze[y-1][x]!='S')
if ((steps[y-1][x]>(step+1) && steps[y-1][x]!=(step-1) ) || steps[y-1][x]==0)
if ( find_path(x, y - 1,step) == TRUE ) return FALSE;
return FALSE;
}
//рекурсивная функция, обходящаа лабиринт с финиша до старта
//по кратчайшему пути
int find_min_path(int x,int y)
{
//если вышли за пределы лабиринта - возвращаемся
if ( x < 0 || x > mCols - 1 || y < 0 || y > nRows - 1 ) return FALSE;
//если данная позиция - не старт и не финиш, то помечаем ее как путь
if (maze[y][x]!='S' && maze[y][x]!='G') {
maze[y][x] = '+';
}
//если дошли до старта - возвращаемся
if ( maze[y-1][x] == 'S' ) return FALSE;
if ( maze[y+1][x] == 'S' ) return FALSE;
if ( maze[y][x-1] == 'S' ) return FALSE;
if ( maze[y][x+1] == 'S' ) return FALSE;
//изнаем расстояния во всех 4-х направлениях
int up = 0;
int right =0;
int left = 0;
int down = 0;
if (y!= 0)
up = steps[y - 1][x];
if (x!= 0)
left =steps[y][x - 1];
if (x!= mCols-1)
right = steps[y][x+1];
if (y!= nRows-1)
down = steps[y+1][x];
//и ищем минимальное
int min = up;
if ((right<min && right!=0) || min==0)
min = right;
if ((left<min && left!=0)|| min==0)
min = left;
if ((down<min && down!=0) || min==0)
min = down;
if (num==0 )
num=min;
//там, где минимальное, туда и идём
if (up==min && up!=0)
if ( find_min_path(x,y - 1) == TRUE ) return TRUE;
if (right==min && right!=0 )
if ( find_min_path(x + 1,y) == TRUE ) return TRUE;
if (left==min && left!=0)
if ( find_min_path(x - 1,y) == TRUE ) return TRUE;
if (down==min && down!=0)
if ( find_min_path(x,y + 1) == TRUE ) return TRUE;
return FALSE;
}
