Can anyone help me to find out why my C++ code does not work?


  • 0
    S

    Below is my code. I tried to use memorized dfs to solve this problem, where the map stores pair<string,int> which means the best path and distance to the hole. But this code fails the 60/64 case:
    [[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1]]
    [29,18]
    [14,22]
    It outputs the incorrect answer: "urululurdrulululul". I don't understand why it cannot find the correct path "ururulululululurul". I need your help. Thanks.

    class Solution {
        int dx[4]={1,0,0,-1};
        int dy[4]={0,-1,1,0};
        string directions[4]={"d","l","r","u"};
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m=maze.size(),n=maze[0].size();
            vector<vector<bool>> Visited(m,vector<bool>(n,false));
            pair<string,int> Paths;
            vector<vector<pair<string,int>>> Map(m,vector<pair<string,int>>(n,{"",INT_MAX}));
            Paths=dfs(Visited,maze,ball[0],ball[1],hole[0],hole[1],m,n,Map);
            return Paths.first;
        }
        pair<string,int> dfs(vector<vector<bool>>& Visited,vector<vector<int>>& maze,int x0,int y0,int x1,int y1,int m,int n,vector<vector<pair<string,int>>>& Map){
            if(!Map[x0][y0].first.empty())return Map[x0][y0];
            vector<pair<string,int>> res={};
            Visited[x0][y0]=true;
            for(int t=0;t<4;t++){
                int xnew=x0,ynew=y0,move=0;
                bool ToSkip=false;
                while(xnew+dx[t]>=0&&xnew+dx[t]<m&&ynew+dy[t]>=0&&ynew+dy[t]<n&&maze[xnew+dx[t]][ynew+dy[t]]==0){
                    xnew+=dx[t];
                    ynew+=dy[t];
                    ++move;
                    if(xnew==x1&&ynew==y1){
                        res.push_back({directions[t],move});
                        ToSkip=true;
                        break;
                    }
                }
                if(ToSkip)break;
                if(Visited[xnew][ynew])continue;
                pair<string,int> Following=dfs(Visited,maze,xnew,ynew,x1,y1,m,n,Map);
                if(Following.first!="impossible"){
                    res.push_back({directions[t]+Following.first,move+Following.second});
                }
            }
            Visited[x0][y0]=false;
            if(res.empty())Map[x0][y0]={"impossible",0};
            if(!res.empty()){
                sort(res.begin(),res.end(),cmp);
                Map[x0][y0]=res[0];
            }
            return Map[x0][y0];
        }
        static bool cmp(pair<string,int>& p1,pair<string,int>& p2){
            return p1.second<p2.second||(p1.second==p2.second&&p1.first<p2.first);
        }
    };
    

  • 0
    S

    Very tricky... Circular path rules out some possible paths incorrectly.


  • 0
    K

    @sanxi
    Can you elaborate a bit more about the circular paths?


  • 0
    S

    @kevin36
    XXXXXXXXXXXXXXXXX
    XXXXXXXXXXDXXXXXX
    XXXXXXXXXXPXXXXXX
    XXXXXXXXXXPXXXXXX
    XXXXXPPPPPAXXXXXX
    XXXXXPXXXXBXXXXXX
    XXXXXPXXXXSXXXXXX
    XXXXXPPPPPPXXXXXX
    XXXXXXXXXXXXXXXXX
    Consider the drawing above, 'X' means wall, all other chars means path, 'S' is the starting postion and D is the destination.
    In my code, it first searches down, then left, then right, and then up. Along the searching path, the place which is previously visited marked as 'Visited'.
    Starting from 'S', it first searches down , and then makes a circle to the place 'A'.
    At 'A', it first searched 'B', but at 'B', both 'A' and 'S' are marked as 'Visited', then now the program marks 'B' as 'impossible'. So when we trace back to S and attempt to go up, 'B' is already marked as 'impossible'. So the true shortest path is overlooked in this way.
    Very tricky.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.