Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. paths(i, j) = paths(i + 1, j) + paths(i, j + 1) when cell (i, j) is open; 0 if it is blocked or outside.
  2. 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));
    }
}

Solve Rat in a Maze online · All practice problems