如何在maz中遞歸找到最長的方法

Question

我已經編寫了一個代碼，以遞歸方式在迷宮中找到並且工作正常。但現在我希望它能從頭到尾找到最長的路。有誰知道我應該如何改變我的算法？ （我仍然希望它是遞歸的） thanx！

#include <iostream> 
#include <vector> 
//#include <string> 
using namespace std; 

const int POSSIBLE_MOVES =4; 
int row_delta[POSSIBLE_MOVES] = {-1,0,1,0}; 
int col_delta[POSSIBLE_MOVES] = {0,1,0,-1}; 
int round=0; 
int way[3][4]={}; 

string map[][4]={"s",".",".","#", 
     "#",".",".","#", 
     "$",".",".","E"}; 


void print_way() 
{ 
    cout<<"PrintWay:\n"; 
    for (int i=0;i<3;++i) 
    { 
     for (int j=0;j<4;++j) 
      cout<<way[i][j]; 
     cout<<endl; 
    } 
    cout<<"\n\n"; 
} 

int find_tour(int move_no, int current_row, int current_col) { 

    cout << move_no << endl; 
    print_way(); 

    if (map[current_row][current_col]=="E") 
     return true; 

    for (int move = 0; move < POSSIBLE_MOVES; move++) { 
     int new_row = current_row + row_delta[move]; 
     int new_col = current_col + col_delta[move]; 

     if (new_row<0 || new_row>=3 || new_col<0 || new_col>=4) 
      continue; 

     if (way[new_row][new_col]!=0) 
      continue; 

    if (map[new_row][new_col]=="#") 
      continue; 

     way[new_row][new_col] = move_no + 1; 
     if (find_tour(move_no + 1, new_row, new_col)) 
      return true; 
     way[new_row][new_col] = 0; 
    } 
    return false; 
} 


int main() 
{ 
    int m=3; //row 
    int n=4; //column 
    int t=1; //number of food 
    int initRow=0; 
    int initCol=0; 

    cout<<"\n\ninput\n\n\n"; 
    cout<<m<<" "<<n<<endl; 
    for (int row=0;row<m;++row)   
    { for (int column=0;column<n;++column) 
      cout<<map[row][column]; 
     cout<<"\n"; 
    } 
    cout<<t<<endl; 
    cout<<"\nnow the functions are calculating:\n"; 

    way[initRow][initCol]=1; 
    find_tour(0,0,0); 
    return 0; 
} 

Answer 1

該算法幾乎相同。但是，當你找到一個退出時，你應該比較找到的路徑的長度，並且如果它比前一個更長，則將其存儲在某個地方。比繼續搜索所有其他可能的方式。 當然，你應該以某種方式標記已經訪問過的點，否則到出口的最長路徑可能會無限長。