Code Logo

Festival Coin Path Count

Published at05 Jan 2026
Created by
Hard 5 views
Like14

You are moving across a grid from the top-left corner to the bottom-right corner. Some cells are blocked, and you are only allowed to move right or down.

The task is to count how many valid paths still exist. A blocked cell cannot be stepped on, so any path that would enter that cell is not allowed.

For example, if grid = [[0,1],[0,0]], the answer is 1 because the path that tries to move right first is blocked, leaving only one valid route. If grid = [[1]], the answer is 0 because even the starting cell is blocked.

So the job is to count all right-and-down routes that avoid every blocked cell.

Example Input & Output

Example 1
Input
grid = [[0,1],[0,0]]
Output
1
Explanation

Only the lower-right path remains open.

Example 2
Input
grid = [[1]]
Output
0
Explanation

The starting stall is blocked, so no path exists.

Example 3
Input
grid = [[0,0,0],[0,1,0],[0,0,0]]
Output
2
Explanation

Two routes skirt the blocked middle stall.

Algorithm Flow

Recommendation Algorithm Flow for Festival Coin Path Count
Recommendation Algorithm Flow for Festival Coin Path Count

Solution Approach

This is a standard grid DP. Let dp[r][c] be the number of valid ways to reach cell (r, c).

If a cell is blocked, then dp[r][c] = 0. Otherwise, the only ways to reach it come from the cell above or the cell to the left:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

The starting cell is a special case: it starts with 1 way if it is open, and 0 if it is blocked.

Once the first row and first column are handled carefully, the rest of the grid fills naturally. The value in the bottom-right cell is the final answer.

This works because every valid path to a cell must arrive from exactly one of those two previous directions.

Best Answers

java

import java.util.*;
class Solution {
    public int festival_coin_path_count(Object grid) {
        int[][] g = (int[][]) grid;
        if (g.length == 0) return 0;
        int m = g.length, n = g[0].length;
        if (g[0][0] == 1) return 0;
        long[] dp = new long[n];
        dp[0] = 1;
        long MOD = 1000000007;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (g[r][c] == 1) dp[c] = 0;
                else if (c > 0) dp[c] = (dp[c] + dp[c-1]) % MOD;
            }
        }
        return (int) dp[n-1];
    }
}