Practice › Recursion & Backtracking
Rat in a Maze
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Paytm, TCS, Infosys
In an n × n grid, 1 is an open cell and 0 is blocked. Count the paths from the top-left to the bottom-right cell moving only right or down through open cells.
Input
First line: n. Next n lines: n values (0 or 1).
Output
The number of paths (0 if the start or end is blocked).
Constraints
- 1 ≤ n ≤ 12
Example 1
Input
3 1 1 1 1 0 1 1 1 1
Output
2
Example 2
Input
2 1 0 0 1
Output
0
Hints
- paths(i, j) = paths(i + 1, j) + paths(i, j + 1) when cell (i, j) is open; 0 if it is blocked or outside.
- The same cell is reached by many routes — memoise paths(i, j) so each cell is solved once.
Approach
Count recursively from the start. A blocked or out-of-grid cell contributes 0, and the bottom-right cell (if open) contributes 1. Otherwise add the counts from moving down and moving right. Without memoisation the recursion follows every path separately (up to C(22, 11) ≈ 7 × 10^5 of them). Caching paths(i, j) makes it O(n²). A blocked start or end gives 0 automatically.
Complexity: O(n²) time · O(n²) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> g;
vector<vector<long long>> memo;
long long paths(int i, int j) {
if (i >= n || j >= n || g[i][j] == 0) return 0;
if (i == n - 1 && j == n - 1) return 1;
if (memo[i][j] != -1) return memo[i][j];
return memo[i][j] = paths(i + 1, j) + paths(i, j + 1);
}
int main() {
cin >> n;
g.assign(n, vector<int>(n));
for (auto &row : g)
for (auto &x : row) cin >> x;
memo.assign(n, vector<long long>(n, -1));
cout << paths(0, 0) << "\n";
return 0;
}Python solution
import sys
from functools import lru_cache
data = list(map(int, sys.stdin.read().split()))
n = data[0]
g = [data[1 + i * n : 1 + (i + 1) * n] for i in range(n)]
@lru_cache(maxsize=None)
def paths(i, j):
if i >= n or j >= n or g[i][j] == 0:
return 0
if i == n - 1 and j == n - 1:
return 1
return paths(i + 1, j) + paths(i, j + 1)
print(paths(0, 0))Java solution
import java.util.*;
public class Main {
static int n;
static int[][] g;
static long[][] memo;
static long paths(int i, int j) {
if (i >= n || j >= n || g[i][j] == 0) return 0;
if (i == n - 1 && j == n - 1) return 1;
if (memo[i][j] != -1) return memo[i][j];
return memo[i][j] = paths(i + 1, j) + paths(i, j + 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
g = new int[n][n];
memo = new long[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
g[i][j] = sc.nextInt();
memo[i][j] = -1;
}
System.out.println(paths(0, 0));
}
}