矩陣遍歷打印全部和最短路徑 - 無限循環

Question

#include<iostream> 
#include<random> 
#include<ctime> 
#include<cstdlib> 
#include<vector> 
#include<algorithm> 
using namespace std; 

int path_checker(vector<pair<int,int> > path, int i, int j) 
{ 
    //cout<<"path_checker"<<endl; 
    std::vector<pair<int, int> >::iterator it; 
    for(it = path.begin(); it!=path.end();it++) 
     if(it->first == i && it->second ==j) 
      return 1; 
    return 0; 
} 

int isVertex(int i, int j, int n) 
{ 
    //cout<<"isVertex"<<endl; 
    if((i>=0) && (j>=0)) 
    { 
     if((i <= n) && (j <= n)) 
      return 1; 
    } 
    return 0; 
} 


void printAllPathsU(int *array, int i, int j, int n, vector<pair<int,int> >  path,int index) 
{ 
    // cout<<"PrintAllPathsU_first"<<endl; 
    // vector<pair<int,int>> path2 = {0}; 
    if((i == n) && (j == n)) 
    { 
     if((path_checker(path,i,j))) 
     { 
     cout<<"Inside printing path"<<endl; 
     //vector<pair<int,int> >::iterator it; 
     for(int i = 0; i < path.size();i++) 
      cout<<"a["<<path[i].first<<"]["<<path[i].second<<"] "; 
     return; 
     } 
     else 
     { 
      path.push_back(make_pair(i,j)); 
      cout<<"Inside printing path"<<endl; 
     //vector<pair<int,int> >::iterator it; 
      for(int i = 0; i < path.size();i++) 
       cout<<"a["<<path[i].first<<"]["<<path[i].second<<"] "; 
      return; 
     } 
    } 
if((*((array+i*n)+j) == 1) && (!path_checker(path,i,j))) 
{ 
    //cout<<path.size()<<endl; 
    path.push_back(make_pair(i,j)); 
    index++; 
    //len++; 
    if(isVertex(i,j-1,n)) 
     printAllPathsU((int *)array,i,j-1,n,path,index); 
    if(isVertex(i-1,j,n)) 
     printAllPathsU((int *)array,i-1,j,n,path,index); 
    if(isVertex(i,j+1,n)) 
     printAllPathsU((int *)array,i,j+1,n,path,index); 
    if(isVertex(i+1,j,n)) 
     printAllPathsU((int *)array,i+1,j,n,path,index); 
} 
else if((*((array+i*n)+j) == 1) && (path_checker(path,i,j))) 
{ 
    //cout<<"inside second else"<<endl; 
    return; 
} 
else if(*((array+i*n)+j) == 0) 
{ 
    // cout<<"inside third else"<<endl; 
    return; 
} 
} 

    void printAllPaths(int *array, int n) 
{ 
vector<pair<int,int> > path; 
//cout<<"PrintALLPaths"<<endl; 
printAllPathsU(array, 0, 0, n, path, 0); 
} 




int main() 
{  //populating matrix 
    int n; 
    cout << "Enter value of n (for n x n matrix): "; 
    cin >> n; 
    int i; 
    int j; 
    int k; 
    int test=1; 
    int array[n][n]; 
    int randomval; 
    int total_elements = n*n; 
    int counter_0 = 0; 
    int max_0 = 0.2 * total_elements; 
    cout << "Number of zeros(20% of n*n) in matrix: "; 
    cout<<max_0<<endl; 
    int count=0; 
    srand(time(0)); 
    for(i = 0;i < n;i++) 
    { 
     for(j = 0;j<n;j++) 
     { 
      array[i][j]=-1; 
     } 
    } 
    while(count < total_elements) 
     { 
      i=rand()%n; 
      j=rand()%n; 
      if(array[i][j]==1 || array[i][j]==0) 
      { 
       continue; 
      } 
      else if(array[i][j] == -1) 
      { 
       count+=1; 
       if(i==0 && j==0) 
       { 
        array[i][j]=1; 
       } 
       else if (counter_0 < max_0) 
       { 
        counter_0+=1; 
        array[i][j] = 0; 
       } 
       else if(counter_0 >= max_0) 
       { 
        test+=1; 
        array[i][j] = 1; 

       } 

      } 
      else{continue;} 
     } 
    cout<<"# of 1s:"<<test<<" & # of 0s:"<<counter_0<<endl; 
    cout<<"Elements Populated:"<<count<<endl; 
    cout<<"Total Elements in matrix:"<<total_elements<<endl; 
    if(counter_0 < max_0) 
    { cout<<"adding more zeros"<<endl; 
     while(k < (max_0 - counter_0)) 
     { 
      i = rand()%n; 
      j = rand()%n; 
      if(array[i][j] == 0) 
      { 

      } 
      else 
      { 
      array[i][j] = 0; 
      k+=1; 
      } 
     } 
    } 
    for(i = 0;i < n;i++) 
    { 
     for(j = 0;j<n;j++) 
     { 
      cout<<array[i][j]<<" "; 
     } 
     cout<<endl; 
    } 


//printing paths 
if(array[1][0]==0 && array[0][1]==0) 
{ 
    cout<<"No Possible paths homie #snorlaxiseverywhere"; 
}else 
{ 
//printing paths 
    printAllPaths((int *)array, n); 
} 
return 0; 
} 

問題是遍歷一個填充有1和0的* n矩陣，其中矩陣中的0的數量是元素總數的20％ ，並使用四個方向：上，下，左和右，打印所有路徑，然後打印從[0] [0]到[n] [n]的最短路徑。 到目前爲止，我試圖實現打印所有可能的路徑。不過，我陷在一個無限循環的

else if((*((array+i*n)+j) == 1) && (!path_checker(path,i,j))) 
{ 
... 
} 

我清點了path.size（）檢查什麼大小成爲每個實例，輸出有點像：

35 
48 
37 
...and so on infinitely (values ranging approx between 30-50) 

任何想法如何糾正？

編輯：改變了一些邏輯，不卡死無限循環。但所有函數調用通過函數printAllPathsU（...）中的「second else」和「third else」退出。

謝謝！

Answer 1

只要問題是如何「打印所有路徑」，您應該有一個無限循環，因爲有無限多的路徑。如果問題是如何打印所有非自相交的路徑，那麼這個改寫提示瞭如何解決問題。