код:
Код:
#include "stdafx.h"
#include <iostream>
#include "time.h"
#include "stdlib.h"
#include "stdio.h"
using namespace std;
const int sX=15;
const int sY=30;//размер лабиринта
bool Volna(int* lab,int kol); //Ф-ция алгоритма "волны"
bool Prior(int* lab,int kol);//ф-ция алгоритма "метод приоритета".
void LabOut(int* lab,char* bl);//вывод лабиринта
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL));
int stop,rnd,labirint[sX][sY];
setlocale(0,"");
char labSet[7]=" %M.";//масив для визуаьного отображения лабиринта
printf("Нажмите ENTER для генерации лабиринта.");
stop = getchar();//генерация лабиринта
for(int i=0;i<sX;i++)
for(int j=0;j<sY;j++)
{ rnd=rand()%4;
labirint[i][j]=rnd; }
for(int t=0;t<2;t++)labirint[rand()%sX][rand()%sY]=4;
cout << "Имеем такой лабиринт\n";
LabOut(&labirint[0][0], labSet);
cout <<"Нахождение пути волновым методом\n";
if(Volna(&labirint[0][0],2))LabOut(&labirint[0][0], labSet);
else cout<<"Нельзя соеденить эти точки\n";
cout <<"Метод приорететов (вправо, влево, вниз, вверх):\n";
if (Prior(&labirint[0][0],2))LabOut(&labirint[0][0], labSet);
else cout <<"Невозможно соеденить эти точки за 250 ходов\n";
cin >> stop;
return 0;
}
bool Volna(int* lab,int kol)
{
int lb[sX][sY];//модифицированая копия лабиринта
int Ni=0, x=0, y=0, copX, copY;//Ni - кольво итераций, x,y,copX,copY - для хранения координат
int min=300, copMin=300; //для поиска минимального пути
bool work=true; //для избежания зацикливания
//заполнения модифицированого лабиринта для волнового метода
for(int i=0;i<sX;i++)
for(int j=0;j<sY;j++)
{
if(*(lab+j+i*sY)/3==0)lb[i][j]=254;
if(*(lab+j+i*sY)==3)lb[i][j]=255;
if(*(lab+j+i*sY)==4)
{
if(kol==2)
lb[i][j]=253;
else
lb[i][j]=0;
kol--;
}
}
//формирование волны
while(work)
{
for(int k=0;k<sX;k++)
for(int l=0;l<sY;l++)
if(lb[k][l]==Ni)
{
if(l+1!=sY)
{
if(lb[k][l+1]==254)
lb[k][l+1]=Ni+1;
if(lb[k][l+1]==253){x=k;y=l+1;work=false;}
}
if(k+1!=sX)
{
if(lb[k+1][l]==254)
lb[k+1][l]=Ni+1;
if(lb[k+1][l]==253){x=k+1;y=l;work=false;}
}
if(l-1!=-1)
{
if(lb[k][l-1]==254)
lb[k][l-1]=Ni+1;
if(lb[k][l-1]==253){x=k;y=l-1;work=false;}
}
if(k-1!=-1)
{
if(lb[k-1][l]==254)
lb[k-1][l]=Ni+1;
if(lb[k-1][l]==253){x=k-1;y=l;work=false;}
}
}
Ni++;
if(Ni==250)work=false;
}
//поиск минимального пути
if(Ni!=250)
{
while(copMin!=0)
{
if(y+1!=sY)
if(min>lb[x][y+1])
{
min=lb[x][y+1];
copY=y+1;
copX=x;
}
if(y-1!=-1)
if(min>lb[x][y-1])
{
min=lb[x][y-1];
copY=y-1;
copX=x;
}
if(x+1!=sX)
if(min>lb[x+1][y])
{
min=lb[x+1][y];
copX=x+1;
copY=y;
}
if(x-1!=-1)
if(min>lb[x-1][y])
{
min=lb[x-1][y];
copX=x-1;
copY=y;
}
x=copX; y=copY; copMin=min; min=300; *(lab + y + x*sY)=5;
}
*(lab + y + x*sY)=4;
}
else return false;
return true;
}
void LabOut(int* lab,char* bl)
{
for(int i=0;i<sX;i++)
{
for(int j=0;j<sY;j++)
cout<<bl[*(lab+j+i*sY)];
cout<<endl;
}
cout<<"--------------------------------------------------------------------------------";
}
bool Prior(int* lab,int kol)
{
int x, y, startX, startY, copX, copY,stop=0; //хранение координат
int lb[sX][sY];//модифицированая копия лабиринта
int min=300;//для нахождения минимального приоритета
bool work=true;//для избежания зацикливания
//создания модифицированого лабиринта под метод приоритетов
for(int i=0;i<sX;i++)
for(int j=0;j<sY;j++)
{
if((*(lab+j+i*sY)/3==0) || (*(lab+j+i*sY)==5)){lb[i][j]=0;*(lab + j + i*sY)=0;}
if(*(lab+j+i*sY)==3)lb[i][j]=255;
if(*(lab+j+i*sY)==4)
{
if(kol==2)
{
lb[i][j]=0;
startX=i;startY=j;
}
else
lb[i][j]=254;
kol--;
}
}
x=startX; y=startY;//хранение точки входа
//реализация алгоритма поиска
while(work)
{
if(y+1!=sY)
{
if(lb[x][y+1]==254)
{work=false; min=0;copY=y+1;copX=x;}
if(min>lb[x][y+1])
{min=lb[x][y+1];copY=y+1;copX=x;}
}
if(y-1!=-1)
{
if(lb[x][y-1]==254)
{work=false; min=0;copY=y-1; copX=x;}
if(min>lb[x][y-1])
{min=lb[x][y-1]; copY=y-1; copX=x;}
}
if(x+1!=sX)
{
if(lb[x+1][y]==254)
{work=false; min=0;copX=x+1; copY=y;}
if(min>lb[x+1][y])
{min=lb[x+1][y]; copX=x+1; copY=y;}
}
if(x-1!=-1)
{
if(lb[x-1][y]==254)
{work=false; min=0;copX=x-1; copY=y;}
if(min>lb[x-1][y])
{min=lb[x-1][y]; copX=x-1; copY=y;}
}
stop++; lb[x][y]++; x=copX; y=copY; min=300; *(lab + y + x*sY)=5;
if(stop==250)work=false;
}
*(lab + startY + startX*sY)=*(lab + y + x*sY)=4;
if(stop==250)work=true;
return !work;
}
Работал в Visual Studio 2010