Count paths in grid with obstacles
Java
Hard
5 views
Problem Description
Task: grid has 0 (free) and 1 (blocked). Return number of paths from (0,0) to (m-1,n-1) moving right/down.
Output Format
Return value
Constraints
Use DP; return 0 if start blocked.
Official Solution
static long countPaths(int[][] g){int m=g.length;int n=m==0?0:g[0].length; if(m==0||n==0) return 0; long[][] dp=new long[m][n]; if(g[0][0]==1) return 0; dp[0][0]=1; for(int i=0;i<m;i++) for(int j=0;j<n;j++){ if(g[i][j]==1){dp[i][j]=0;continue;} if(i==0&&j==0) continue; long up=i>0?dp[i-1][j]:0; long left=j>0?dp[i][j-1]:0; dp[i][j]=up+left;} return dp[m-1][n-1];}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!