Backtrack으로 미로 해결하기

Question

txt 파일을 통해 미로를받는 프로젝트가 있는데 해결해야합니다. 해결할 수있는 유일한 하드 사양은 다음과 같습니다. 다른 이차원 배열 없음 (복사 금지, 부울 없음).

그래서 스택과 백 트랙킹을 사용하여 문제를 해결합니다. 나는 두 개의 스택을 사용하는데 하나는 방문한 방을 복사하는 것이고 다른 하나는 경로를 복사하는 것이다. 하지만 중요한 점은 내가 메인 함수로 돌아 왔을 때, 두 스택은 미로에있는 마지막 위치에 있다는 것입니다. 그래서 제 문제입니다, 제 자리에서 마지막 위치에 있습니다.

내가 역 추적 기능을 사용할 때 이전에 언급했던 스택을 테스트하고 잘 작동하는 스택 (방문한 스택을 저장하는 스택)을 테스트 할 수있는 또 다른 기능이 있습니다. 이 스택의 값.

주 기능이 전체 스택 (최소한 방문한 객실의 경우)을받을 수없는 이유는 모르지만 경로 스택은 전혀 작동하지 않습니다.

경로 스택을 변경해야하지만 어쨌든 작동하지 않습니다.

그래프를 사용하여 문제를 해결한다고 생각하지만 그래프를 구현하는 방법을 모르겠습니다. 유감스럽게 생각하는 영어 실력, 나는 영어 원어민이 아니다. 나는 어떤 단어를 코드로 바꾸려고 노력했다. 스페인어로 된 몇몇 단어가 원인이되었다. 어떤 도움이라도 좋을 것입니다. .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 

Answer 1

코드에 많은 문제가 있으며 그 중 일부는 중요하며 일부는 효율성 문제입니다. 지금 볼 수있는 주요 문제는 분석 코드가 아니라 진단 코드입니다. 코멘트의 부분에서

봐 :

/* CODE TO CHECK visited Rooms */ 
    Nodo *temp = new Nodo(); 
    temp=pileDG->tope; 
    while(temp!=NULL){ 
     cout << temp->row <<" "<<temp->col << endl; 
     getchar(); 
     temp->pre; 
    } 

닫는 중괄호 전에 마지막 줄은 그냥 *temp 개체에서 pre 필드를 읽고

 temp->pre; 

이지만, 는 없습니다에게 사용합니까 그 값 - temp 변수가 수정되지 않으므로 프로그램이 반복적으로 루프에 머물러있어 동일한 데이터가 반복해서 인쇄됩니다.

나는

 temp = temp->pre; 

당신이 무엇을 의미하는지 것 같다.

/* CODE TO CHECK visited Rooms */ 
    for(Nodo *temp=pileDG->tope; temp!=NULL; temp=temp->pre){ 
     cout << temp->row <<" "<<temp->col << endl; 
     getchar(); 
    } 

당신은 당신이 가능하게 볼 (의 일부)를 교체 코드 다른 문제되면 : 당신이 for 대신 while를 사용하는 경우

어쨌든 이러한 루프는 쓰기와 읽기 쉽다. 예를 들어 인쇄물에 너무 많은 '방문'위치가있을 수 있습니다.

Answer 2

?

Node * recor; 
recor = new Node(); 
recor = pileDG->top; 

새 노드를 영원히 잃어 버리지 않았습니까?

방문한 모든 새로운 지점을 colaDG 스택에 배치하는 것처럼 보입니다. 그러나 막 다른 길에서 다시 추적 할 때 지점을 제거하는 위치를 볼 수 없습니다.