Count paths in grid with obstacles
Hard
Java
Control Flow
24 views
Problem Statement
Task: grid has 0 (free) and 1 (blocked). Return number of paths from (0,0) to (m-1,n-1) moving right/down.
Input Format
Two integers m and n (rows and columns)
Then an m × n grid where:
• 0 = free cell
• 1 = blocked cell
Then an m × n grid where:
• 0 = free cell
• 1 = blocked cell
Output Format
An integer: number of valid paths from (0,0) to (m-1,n-1)
(moving only right or down)
(moving only right or down)
Example
3 3 0 0 0 0 1 0 0 0 0
2
Constraints
• m ≥ 1, n ≥ 1
• Start (0,0) and end (m-1,n-1) must be free (0)
• Moves allowed: right or down only
• Start (0,0) and end (m-1,n-1) must be free (0)
• Moves allowed: right or down only
Concept Explanation
We count paths while avoiding blocked cells.
Each cell’s paths = paths from top + paths from left
(if the cell is not blocked).
Each cell’s paths = paths from top + paths from left
(if the cell is not blocked).
Step-by-Step Explanation
1.Read m, n, and the grid.
2.Create a 2D array dp[m][n] to store number of paths.
3.If start cell (0,0) is blocked, return 0.
4.Set dp[0][0] = 1.
5.Fill first row:
• If a cell is blocked, paths = 0.
• Else, paths come from the left cell.
6.Fill first column similarly (paths come from top).
7.For each cell (i, j) starting from (1,1):
• If grid cell is blocked: dp[i][j] = 0.
• Else: dp[i][j] = dp[i-1][j] + dp[i][j-1].
8.Return dp[m-1][n-1].
2.Create a 2D array dp[m][n] to store number of paths.
3.If start cell (0,0) is blocked, return 0.
4.Set dp[0][0] = 1.
5.Fill first row:
• If a cell is blocked, paths = 0.
• Else, paths come from the left cell.
6.Fill first column similarly (paths come from top).
7.For each cell (i, j) starting from (1,1):
• If grid cell is blocked: dp[i][j] = 0.
• Else: dp[i][j] = dp[i-1][j] + dp[i][j-1].
8.Return dp[m-1][n-1].
Concept Explanation
We count paths while avoiding blocked cells.
Each cell’s paths = paths from top + paths from left
(if the cell is not blocked).
Each cell’s paths = paths from top + paths from left
(if the cell is not blocked).
Step-by-Step Explanation
1.Read m, n, and the grid.
2.Create a 2D array dp[m][n] to store number of paths.
3.If start cell (0,0) is blocked, return 0.
4.Set dp[0][0] = 1.
5.Fill first row:
• If a cell is blocked, paths = 0.
• Else, paths come from the left cell.
6.Fill first column similarly (paths come from top).
7.For each cell (i, j) starting from (1,1):
• If grid cell is blocked: dp[i][j] = 0.
• Else: dp[i][j] = dp[i-1][j] + dp[i][j-1].
8.Return dp[m-1][n-1].
2.Create a 2D array dp[m][n] to store number of paths.
3.If start cell (0,0) is blocked, return 0.
4.Set dp[0][0] = 1.
5.Fill first row:
• If a cell is blocked, paths = 0.
• Else, paths come from the left cell.
6.Fill first column similarly (paths come from top).
7.For each cell (i, j) starting from (1,1):
• If grid cell is blocked: dp[i][j] = 0.
• Else: dp[i][j] = dp[i-1][j] + dp[i][j-1].
8.Return dp[m-1][n-1].
Input / Output Format
Input Format
Two integers m and n (rows and columns)
Then an m × n grid where:
• 0 = free cell
• 1 = blocked cell
Then an m × n grid where:
• 0 = free cell
• 1 = blocked cell
Output Format
An integer: number of valid paths from (0,0) to (m-1,n-1)
(moving only right or down)
(moving only right or down)
Constraints
• m ≥ 1, n ≥ 1
• Start (0,0) and end (m-1,n-1) must be free (0)
• Moves allowed: right or down only
• Start (0,0) and end (m-1,n-1) must be free (0)
• Moves allowed: right or down only
Examples
Input:
3 3
0 0 0
0 1 0
0 0 0
Output:
2
Example Solution (Public)
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];}
Official Solution Code
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];}
Please login to submit solutions.