Valid paths in a grid using Recursion
Idea is to use a recursive approach to explore all possible paths from the starting cell to the ending cell and check if the unique and valid paths.
Steps to solve the problem:
- Start from the top-left cell
(0, 0). - Recursively explore two paths:
- Move down from
(i, j)to(i+1, j)if it’s a valid path. - Move right from
(i, j)to(i, j+1)if it’s a valid path.
- Move down from
- If
(i, j)reaches the bottom-right cell(m-1, n-1), increment the count of valid paths.
Below is the implementation of the approach:
#include <iostream>
#include <vector>
using namespace std;
// Function to count the number of paths from (i, j) to
// bottom-right
int countPaths(const vector<vector<int> >& grid, int i,
int j)
{
// Base case: if out of bounds or obstacle encountered
if (i >= grid.size() || j >= grid[0].size()
|| grid[i][j] == 0)
return 0;
// If reached the bottom-right cell
if (i == grid.size() - 1 && j == grid[0].size() - 1)
return 1;
// Move down and right
return countPaths(grid, i + 1, j)
+ countPaths(grid, i, j + 1);
}
int main()
{
vector<vector<int> > grid1 = { { 1, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 0, 1, 1, 1 } };
vector<vector<int> > grid2 = { { 1, 1 }, { 1, 1 } };
cout << countPaths(grid1, 0, 0)
<< endl; // Output for grid1
cout << countPaths(grid2, 0, 0)
<< endl; // Output for grid2
return 0;
}
// This code is contributed by Ayush Mishra
public class Main {
public static int countPathsNaive(int[][] grid, int i,
int j)
{
// Base case: if out of bounds or obstacle
// encountered
if (i >= grid.length || j >= grid[0].length
|| grid[i][j] == 0) {
return 0;
}
// If reached the bottom-right cell
if (i == grid.length - 1
&& j == grid[0].length - 1) {
return 1;
}
// Move down and right
return countPathsNaive(grid, i + 1, j)
+ countPathsNaive(grid, i, j + 1);
}
public static void main(String[] args)
{
int[][] grid1 = { { 1, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 0, 1, 1, 1 } };
System.out.println(countPathsNaive(grid1, 0, 0));
int[][] grid2 = { { 1, 1 }, { 1, 1 } };
System.out.println(countPathsNaive(grid2, 0, 0));
}
}
def count_paths_naive(grid, i, j):
# Base case: if out of bounds or obstacle encountered
if i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
return 0
# If reached the bottom-right cell
if i == len(grid) - 1 and j == len(grid[0]) - 1:
return 1
# Move down and right
return count_paths_naive(grid, i+1, j) + count_paths_naive(grid, i, j+1)
grid1 = [
[1, 0, 0, 0],
[1, 1, 1, 1],
[0, 0, 1, 0],
[0, 1, 1, 1]
]
print(count_paths_naive(grid1, 0, 0))
grid2 = [
[1, 1],
[1, 1]
]
print(count_paths_naive(grid2, 0, 0))
function countPathsNaive(grid, i, j) {
// Base case: if out of bounds or obstacle encountered
if (i >= grid.length || j >= grid[0].length || grid[i][j] === 0) {
return 0;
}
// If reached the bottom-right cell
if (i === grid.length - 1 && j === grid[0].length - 1) {
return 1;
}
// Move down and right
return countPathsNaive(grid, i + 1, j) + countPathsNaive(grid, i, j + 1);
}
let grid1 = [
[1, 0, 0, 0],
[1, 1, 1, 1],
[0, 0, 1, 0],
[0, 1, 1, 1]
];
console.log(countPathsNaive(grid1, 0, 0));
let grid2 = [
[1, 1],
[1, 1]
];
console.log(countPathsNaive(grid2, 0, 0));
Output
1 2
Time Complexity: O(2m+n) where m is the number of rows and n is the number of columns.
Auxiliary Space: O(m+n) for the recursion stack.
Valid paths in a grid in Python
Given a 2D grid of 0s (obstacles) and 1s (valid paths), find the number of valid paths from the top-left corner to the bottom-right corner. You can only move down or right.
Examples:
Input: grid = [ [1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output:2Input: grid = [ [1, 1], [1, 1]]
Output:1