У меня есть проект, который получает лабиринт через текстовый файл, и мне нужно его решить. Единственные сложные спецификации для ее решения: нет другого двумерного массива (без копирования, без логического значения).
Поэтому я использую стеки и поиск с возвратом, чтобы решить эту проблему. Я использую два стека, один для копирования посещенных комнат, а другой для копирования пути. Но дело в том, что когда я возвращаюсь к основной функции, две стопки занимают только последнюю позицию в лабиринте. Так что это моя проблема, только что получил последнюю позицию в своих стеках.
Когда я нахожусь в функции возврата, есть еще одна функция, которая проверяет, был ли я в этой позиции раньше, я проверяю стек, о котором я упоминал ранее, и работает нормально (стек, который сохраняет посещенные комнаты), я распечатал все значения этого стека .
Я не знаю, почему основная функция не может получить полный стек (по крайней мере, для посещенных комнат), стек путей вообще не работает.
bool path(ColaD* colaDG, Node* temp, PileD* pileDG)
{
if (temp->row == colaDG->end->row && temp->col == colaDG->end->col)
return true;
if (check(pileDG, temp) || mat[temp->row][temp->col] == 1)
{
// call check function
return false;
}
pileDG->push(*temp);
if (temp->row != 0)
{
temp->row -= 1;
colaDG->push(*temp);
if (path(colaDG, temp, pilaDG))
{
return true;
}
temp->row += 1;
}
if (temp->row != n - 1)
{
temp->row += 1;
colaDG->push(*temp);
if (path(colaDG, temp, pilaDG))
{
return true;
}
temp->row -= 1;
}
if (temp->col != 0)
{
temp->col -= 1;
colaDG->push(*temp);
if (path(colaDG, temp, pilaDG))
{
return true;
}
temp->col += 1;
}
if (temp->col != m - 1)
{
temp->col += 1;
colaDG->push(*temp);
if (path(colaDG, temp, pilaDG))
{
return true;
}
temp->col -= 1;
}
return false;
}
bool check(PileD* pileDG, Node* temp)
{
// Function to check visited rooms
bool flag = false;
Node * recor;
recor = new Node();
recor = pileDG->top;
while (recor != NULL)
{
if (recor->row == temp->row && recor->col == temp->col)
{
// if already here, return true
flag = true;
break;
}
else
recor = recor->pre;
}
return flag;
}
Мне нужно изменить стек пути, я знаю, но все равно не работает.
Я думаю об использовании графа для ее решения, но я вообще не знаю, как реализовать граф. Извините за мой английский, я не носитель английского языка. Я попытался изменить некоторые слова в коде, потому что некоторые слова были на испанском языке. Любая помощь будет здорово. И извините за весь код в .cpp файле, я просто тестирую, реальный проект будет другим.
Полный код:
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
int n=0,m=0;
int **mat;
class Node{
public:
Node(){pre=NULL;}
int row;
int col;
Node *pre;
};
class ColaD{
public:
ColaD(){fin=fte=end=NULL;}
void push(Nodo xdato);
void pop();
Node *fte,*fin,*end;
};
void ColaD::push(Node xdato){
Node *nuevo;
nuevo = new Node();
if(nuevo){
(*nuevo)= xdato;
nuevo->pre = NULL;
if(!fte)
fte = nuevo;
else
fin->pre=nuevo;
fin = nuevo;
}
}
void ColaD::pop(){
Node *elim;
if(fte){
elim = fte;
if(fte==fin)
fte = fin = NULL;
else
fte = fte->pre;
delete(elim);
}
}
class PileD{
public:
PileD(){tope=NULL;}
void push(Node xdato);
void pop();
Node *tope;
};
void PilaD::push(Node xdato){
Node *nuevo;
nuevo = new Node;
if(nuevo){
(*nuevo)=xdato;
nuevo->pre=tope;
tope=nuevo;
}
}
void PileD::pop(){
Node *aux;
if(tope){
aux=tope;
tope=tope->pre;
free(aux);
}
}
void tamMat(); //read the size of the maze given by a txt file
void loadM(); //once i know the size, and the bi dimensional is created I set the values to de bi dimensional A.
void printM(); //Just check the values
bool path(ColaD *colaDG,Node *temp,PileD *pileDG);
bool check(PileD *pileDG,Node *temp);
int main(int argc, char const *argv[])
{
ColaD *colaDG;
Node *inicio;
PileD *pileDG;
tamMat(); //Read the size
mat = new int*[n];
for(int i=0;i<n;i++)
mat[i]=new int[m];
loadM(); //Set values given from the file
colaDG = new ColaD();
pileDG = new PileD();
inicio = new Node();
inicio->row=0; //Proyect says, the start of the maze is in the first row of the maze
for(int j=0;j<m;j++)
if(mat[0][j]!=1){
inicio->col=j; //Found the position in the row
break;
}
colaDG->end = new Nodo();
colaDG->end->row=n-1; //End position is in the last row
for(int j=0;j<m;j++)
if(mat[n-1][j]!=1){
colaDG->end->col=j; //Found the position
break;
}
bool b = path(colaDG,inicio,pilaDG); //call my backtrack function
getchar();
/* CODE TO CHECK visited Rooms
Nodo *temp = new Nodo();
temp=pileDG->tope;
while(temp!=NULL){
cout << temp->row <<" "<<temp->col << endl;
getchar();
temp->pre;
}
*/
getchar();
return 0;
}
void tamMat(){
fstream inFile;
int num;
n=m=0;
inFile.open("mat.txt",ios::in);
string line;
getline(inFile,line);
stringstream temp(line);
while(temp>> num)
m++;
n++;
while(getline(inFile,line))
n++;
inFile.close();
}
void loadM(){
fstream inFile;
inFile.open("mat.txt",ios::in);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
inFile >> mat[i][j];
inFile.close();
}
void printM(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]!=1)
cout << " ";
else
cout << mat[i][j];
cout << " ";
}
cout << endl;
}
}
bool path(ColaD *colaDG,Node *temp,PileD *pileDG){
if(temp->row==colaDG->end->row && temp->col==colaDG->end->col) return true;
if(check(pileDG,temp) || mat[temp->row][temp->col]==1){
return false;
}
pileDG->insertar(*temp);
if(temp->row!=0){
temp->row-=1;
colaDG->insertar(*temp);
if(path(colaDG,temp,pileDG)){
return true;
}
temp->row+=1;
}
if(temp->row!=n-1){
temp->row+=1;
colaDG->insertar(*temp);
if(path(colaDG,temp,pileDG)){
return true;
}
temp->row-=1;
}
if(temp->col!=0){
temp->col-=1;
colaDG->insertar(*temp);
if(path(colaDG,temp,pileDG)){
return true;
}
temp->col+=1;
}
if(temp->col!=m-1){
temp->col+=1;
colaDG->insertar(*temp);
if(path(colaDG,temp,pileDG)){
return true;
}
temp->col-=1;
}
return false;
}
bool check(PileD *pileDG,Node *temp){
bool flag=false;
Node *recor;
recor = new Node();
recor = pileDG->tope;
while(recor!=NULL){
if(recor->row==temp->row && recor->col==temp->col){
flag=true;
break;
}
else
recor=recor->pre;
}
return flag;
}
Файл лабиринта mat.txt.
0 0 0 1 1 1 1 1 1 1
1 1 0 1 0 5 1 1 0 1
1 1 6 1 7 1 1 1 0 1
1 1 0 1 0 1 0 0 0 1
1 0 9 0 0 1 0 1 0 1
1 8 1 1 0 1 6 1 0 1
1 0 1 1 0 1 0 1 5 1
1 0 1 1 0 1 0 1 0 1
1 0 0 1 0 0 0 1 7 1
1 1 1 1 1 1 1 1 0 1
1=Walls / 0=Free Space / Other numbers = Bonus