0
我有一个项目，通过txt文件接收迷宫，我必须解决它。 解决它的唯一硬规格是：没有其他的二维阵列（无副本，无布尔）。问题解决与回溯迷宫
所以我使用堆栈和回溯来解决它。我使用两个堆栈，一个用于复制访问的房间，另一个用于复制路径。但事情是，当我回到主要功能时，这两个筹码只能在迷宫中获得最后的位置。所以这就是我的问题，只是在我的筹码中获得了最后的位置。
当我在回溯函数中时，还有另一个函数用于检查我是否处于该位置，测试之前提到的堆栈，并且工作正常（保存所访问房间的堆栈），我全部打印这个堆栈的值。
我不知道为什么主函数不能接收完整的堆栈（至少对于访问过的房间），路径堆栈根本不工作。
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
似乎有一些问题在页面右侧的相关栏目中与您的问题非常相似......这是第一个问题......不确定这是否有帮助，但看到对方拥有相同的标题，必然会有你的答案。 –