各位dl看过来~迷宫的路径数量不对

Question

各位da佬，求问迷宫问题，找最短路径长度以及其条数，按给定初始化应该只有一条为长度为5的路径，为啥会多出来一条？

//目前无法解决最短路径条数的问题
#include<iostream>
#include<vector>
using namespace std;

class PathFinder{
    private:
        int rows, cols;//map的行数和列数
        int startx, starty;//起点坐标
        int endx, endy;//终点坐标
        int pathNum;//最短路径数
        int minDistance;//最短路径长度
        int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
        vector<vector<int>> map;//地图矩阵,0为空地，1为障碍
        vector<vector<int>> visit;//访问记录，0为未访问，1为障碍或已访问

        void dfs(int row, int col, int distance){
            if(row==endx && col==endy){
                if(minDistance>distance){
                    minDistance=distance;
                    pathNum=1;
                }
                else if(minDistance==distance){
                    pathNum+=1;
                }
                return;
            }
            
            //处理当前坐标
            for(int i=0; i<4; i++){
                int nextRow=row+dx[i], nextCol=col+dy[i];
                if(nextRow>=0 && nextRow<rows && nextCol>=0 && nextCol<cols && visit[nextRow][nextCol]==0){
                    visit[nextRow][nextCol]=1;
                    dfs(nextRow, nextCol, distance+1);
                    visit[nextRow][nextCol]=0;
                }
            }
        }//深度优先搜索
            

    public:
        void mazeEnter(){
            cin>>startx>>starty;
            cin>>endx>>endy;
            cin>>rows>>cols;
            for(int i=0; i<rows; i++){
                vector<int> oneRow;
                for(int j=0; j<cols; j++){
                    int elem;
                    cin>>elem;
                    oneRow.push_back(elem);
                }
                map.push_back(oneRow);
            }
            visit=map;
            pathNum=0;
            minDistance=INT_MAX;//有时候用不了
        }//输入初始化

        

        vector<int> mazeResult(){
            dfs(startx, starty, 0);
            if(minDistance==INT_MAX) minDistance=0;
            vector<int> result(2);
            result[0]=minDistance;
            result[1]=pathNum;
            return result;
        }//返回最短路径长度和数量

        void mazeInitial(){
            startx=0, starty=1;
            endx=3, endy=3;
            rows=4, cols=4;
            map={
                {1,0,1,1},
                {1,0,1,1},
                {1,0,0,0},
                {1,0,0,0}};
            visit=map;
            pathNum=0;
            minDistance=INT_MAX;
        }//给定初始化

        int mazeTest(){
            dfs(startx, starty, 0);
            return visit[0][3];
        }
};

int main(){
    PathFinder sol;
    //sol.mazeEnter();
    sol.mazeInitial();
    cout<<"The minimum distance is: "<<sol.mazeResult()[0]<<endl;
    cout<<"The number of shortest paths is: "<<sol.mazeResult()[1]<<endl;
    cout<<"The Test result is: "<<sol.mazeTest()<<endl;
    return 0;
}

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。