c++ - 矩阵遍历打印所有和最短路径 - 无限循环

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 * 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(...)。

谢谢!

Answer 1

只要问题是如何“打印所有路径”，你就应该有一个无限循环，因为有无限多条路径。如果问题是如何打印所有非自相交路径，那么这种改写会提示如何着手解决问题。