Суть задачи: даны матрица NxM, даны 2 точки точка входа в лабиринт и выхода(пока отрубил,беру поиск с верхней точки), необходимо пройтись по лабиринту и найти путь до выхода, если выхода нет то соответствующее сообщение, необязательно находить кратчайший путь, вывести эту же матрицу но с обозначением пройденного пути от начала к концу(любым символом),так то его надо в файл(но пока ладно),в данной матрице одна развилка беру пока без стека для проверки матрицу...
Беру для проверки матрицу:
1,1,0,1,1,
0,0,0,0,1,
1,1,1,0,1,
1,1,1,0,1,
1,1,1,0,1
если pDown(); поднять выше то все работает, для этой матрицы
| Код |
#include <iostream>
#include <stack>
using namespace std;
//пока почти все переменные глобальные - позже в нормальный вид...
//вводим матрицу 5х5
int const mkY=5;
int const mkX=5;
//чтобы пока -1 не ставить везде
int kY=mkY-1;
int kX=mkX-1;
int mat[mkY][mkX]={
1,1,0,1,1,
0,0,0,0,1,
1,1,1,0,1,
1,1,1,0,1,
1,1,1,0,1
};
int posX = 0,
posY = 0;
//Переменные
//пустота
//стена
//позиция старта
//позиция выхода
//Функции
void pLeft(void)//влево
{
if(mat[posY][posX-1]==0)
{
mat[posY][posX]=1;
posX--;
};
};
void pRight(void)//вправо
{
if( (mat[posY][posX+1]==0) && (posX+1!=kX) )
{
mat[posY][posX]=1;
posX++;
};
};
void pDown(void)//вниз
{
if(mat[posY+1][posX]==0)
{
mat[posY][posX]=1;
posY++;
};
};
void pBottom(void)//вверх
{
if(mat[posY-1][posX]==0)
{
mat[posY][posX]=1;
posY--;
};
};
int main(int argc, char* argv[])
{
//Выводит массив на экран
for(int i = 0; i <= kY; i++)
for(int j = 0; j<= kX; j++)
{
cout << mat[i][j] << ' ' ;
if (j == kX) cout << endl;
};
cout << "- - - - - - -" << endl;
int ST[2] = {0,1}, // 1.2 _start
EN[2] = {4,2}; // 5.3 _end
// int posX = 0,
// posY = 0;
posY = ST[0]; //позиция старта Строки X
posX = ST[1]; //позиция старта Столбца Y
cout << "coordinats START: "<< posY << " " << posX << endl;
cout << "coordinats END: "<< EN[0] << " " << EN[1] << endl;
int kontr(0);
posX=0;
posY=0;
/* !!! нахождение точки выхода по углам, в ином случаи "Выхода нет!" */
//ищем точку входа сверху,
for (int j=0;j >= kX ;j++ )
if (mat[0][j]==0){
cout << 'z'<< posX <<endl;
posX=j;
cout << 'j'<< j <<endl;
};
for(int i=0; i <= kX;i++)
if (mat[0][i]==0)posX=i;
//тестовые переменные
int tm[10][10];//вместо стека
int tt = 0;
//mat[posY][posX]=1;
while (kontr!=1)
{
//для проверки while, т.к условие в нём не работает!
//if ((posY >= EN[0])&&(posX >= EN[1] ))kontr=1;
if ((posY >= kY)&&(posX >= 1 ))kontr=1;
cout << "Y=" << posY << " X=" << posX << endl;
if(mat[posY][posX]==0)//текущая позиция ? = 0
{
//если после движения везде 1
if( ((mat[posY+1][posX]==1)&&(mat[posY-1][posX]==1)&&(mat[posY][posX+1]==1)&&(mat[posY][posX-1]==1))&&(tt>=1) )
{
mat[posY][posX]=1;
posY = tm[0][0];
posX = tm[0][1];
mat[posY][posX]=0;
cout<< "C>> " << "Y=" << posY << "X=" << posX <<endl;
//tt --;
tt = 0;
//проверка не пустой ли стек, если да то прохода нет
};
//если после движения Д 0
if((posY<=kY)&&
(
((mat[posY ][posX+1]==0)&&(mat[posY ][posX-1]==0))||//справа слева
((mat[posY+1][posX ]==0)&&(mat[posY ][posX+1]==0))||//сверху справа
((mat[posY+1][posX ]==0)&&(mat[posY-1][posX ]==0))||//сверху снизу
((mat[posY+1][posX ]==0)&&(mat[posY ][posX-1]==0))||//сверху слева
((mat[posY ][posX+1]==0)&&(mat[posY-1][posX ]==0))||//справа снизу
((mat[posY ][posX-1]==0)&&(mat[posY-1][posX ]==0)) //слева снизу
)
)
{
//сохранить позиции x y
tm[0][0] = posY;
tm[0][1] = posX;
cout << "S<<" << " Y=" << posY << "X=" << posX <<endl;
tt = 1;
//сохраняем позицию в стек
//tt ++;
};
pDown();//вниз
pLeft();//влево
pRight();//вправо
};
};
cout << endl << "test END";
getchar();
return 1;
}
|
|