What's wrong with my implementation?


  • 0
    G

    The test cases of [[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]] returned runtime error

    Code is below:

      class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
            vector<vector<int>> myth(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(),-1));
            for(int i = 0;i<myth.size();i++)
                for(int j = 0;j<myth[0].size();j++)
                {
                    if(obstacleGrid[i][j]==0)  
                        myth[i][j] = -1;
                    else
                        myth[i][j] = 0;
                }
            myth[0][0] = 1;
                for(int i = 1;i<myth.size();i++)
                {
                    if(myth[i][0]==0)
                        continue;
                    myth[i][0] = myth[i-1][0];
                }
                for(int i = 1;i<myth[0].size();i++)
                {
                    if(myth[0][i]==0)
                        continue;
                    myth[0][i] = myth[0][i-1];
                }
            for(int i = 1;i<myth.size();i++)
                for(int j = 1;j<myth.size();j++)
                {
                    if(myth[i][j] == 0)
                        continue;
                    
                    myth[i][j] = myth[i-1][j]+myth[i][j-1];
                }
            return myth[myth.size()-1][myth[0].size()-1];
            //return 1;
        }
    };

  • 0
    S

    Could you please update your post, with some algorithm explanation and comments in code?


  • 2
    R

    Your problem is here:

      for(int i = 1;i<myth.size();i++)
            for(int j = 1;j<myth.size();j++)
    

    You are using myth.size() for both dimensions. This is going to fail anytime the grid isn't square. The second one should be myth[0].size() instead.


  • 1
    Y

    The solution here is similar to the Problem of Unique Path,except that when it meets an obstacle,reset the counter to zeros.

    class Solution {
        public:
            int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
                int m=obstacleGrid.size();
                if(m==0) return 0;
                int n=obstacleGrid[0].size();
                if(n==0) return 0;
                vector<int> res(n+1,0);
                res[1]=1;
                for(int i=0;i<m;i++)
                    for(int j=1;j<=n;j++){
                        if(!obstacleGrid[i][j-1])
                        res[j]+=res[j-1];
                        else
                        res[j]=0;
                    }
                return res[n];    
            }
        };

  • 0
    S

    Hey @yxcyangxuecheng, thanks for your sharing. Even though your code looks elegant, words to clarify thoughts are never too much.


Log in to reply
 

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