Grid Paths I

Grid Paths I
CSES easy

Consider an \(n \times n\) grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square. You can only move right or down.

Input:

  • First line: integer \(n\) — the size of the grid.
  • Next \(n\) lines: each has \(n\) characters:
    • . denotes an empty cell
    • * denotes a trap

Output:

  • Print the number of valid paths modulo \(10^9 + 7\).

Constraints:

  • \(1 \le n \le 1000\)

Example:

Input:

4
....
.*..
...*
*...

Output:

3

Solution

We want to count paths from \((0,0)\) to \((n-1,n-1)\), moving only right or down, and never stepping on a *.

This is a standard grid DP:

DP idea (sequential)

Let dp[i][j] be the number of ways to reach cell \((i,j)\) from \((0,0)\).

  • If cell \((i,j)\) is a trap: dp[i][j] = 0.
  • Otherwise, we can arrive from:
    • above: \((i-1,j)\) by moving down,
    • left: \((i,j-1)\) by moving right.

So for an empty cell:

\(dp[i][j] = \begin{cases} 1 & \text{if } i = 0, j = 0 \text{ and not a trap},\\[4pt] \big(dp[i-1][j] + dp[i][j-1]\big) \bmod M & \text{otherwise}, \end{cases}\)

where \(M = 10^9 + 7\).

We fill the table sequentially, with nested loops:

  • i from 0 to n-1,
  • j from 0 to n-1.

The answer is dp[n-1][n-1].

SRTBOT proof

We’ll structure the correctness using the SRTBOT framework:

S — State

dp[i][j] = number of valid paths from the start cell \((0,0)\) to cell \((i,j)\), obeying:

  • only moves right or down,
  • never entering a trap (*).

This is exactly what we ultimately want for \((n-1,n-1)\).

R — Recurrence

For a non-trap cell \((i,j)\) (i.e. grid[i][j] == '.'):

  • Any path to \((i,j)\) must come from above \((i-1,j)\) or from left \((i,j-1)\), since moves are only right or down.
  • There are no other ways to enter \((i,j)\).

Therefore:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1] \pmod M,\)

where out-of-bounds indices contribute 0.

If grid[i][j] == '*':

\(dp[i][j] = 0,\)

since we cannot stand on traps.

T — Transition

In code, for each cell:

if (grid[i][j] == '*') dp[i][j] = 0;
else if (i == 0 && j == 0) dp[i][j] = 1;
else {
    long long from_up   = (i > 0 ? dp[i-1][j] : 0);
    long long from_left = (j > 0 ? dp[i][j-1] : 0);
    dp[i][j] = (from_up + from_left) % MOD;
}

This directly implements the recurrence above.

B — Base cases

  • Start cell:

    • If (0,0) is a trap → no paths at all → dp[0][0] = 0 (handled by trap rule).

    • If (0,0) is empty → exactly one way to “start” there:

      \(dp[0][0] = 1.\)

  • First row (i = 0, j > 0):

    • Can only come from the left (since there is no row above).

    • Our recurrence with dp[i-1][j] = 0 automatically gives:

      \(dp[0][j] = dp[0][j-1] \text{ if not trap, else } 0.\)

  • First column (j = 0, i > 0):
    • Can only come from above; similarly handled by dp[i][j-1] = 0.

Thus all special cases are correctly covered by the general rules plus boundary checks.

O — Order of computation

We iterate (i,j) in row-major order:

  • Outer loop: i = 0..n-1
  • Inner loop: j = 0..n-1

When computing dp[i][j], we only use:

  • dp[i-1][j] (previous row),
  • dp[i][j-1] (previous column of the same row),

both of which have already been computed because:

  • i-1 < i (previous row),
  • j-1 < j (previous column in the same row).

So all dependencies are computed before they are used — the DP is well-defined.

T — Time and space complexity

  • There are \(n^2\) cells.
  • For each cell, we do \(O(1)\) work.

So:

  • Time: \(O(n^2)\) (at most \(10^6\) operations → fine).
  • Space: \(O(n^2)\) for the DP table.

Final answer

The value dp[n-1][n-1] is exactly the number of valid paths from top-left to bottom-right, modulo \(10^9+7\).

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // dp[i][j] = number of ways to reach (i, j)
    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '*') {
                dp[i][j] = 0; // cannot use traps
                continue;
            }

            if (i == 0 && j == 0) {
                dp[i][j] = 1; // starting cell (if not trap)
            } else {
                long long from_up   = (i > 0 ? dp[i - 1][j] : 0);
                long long from_left = (j > 0 ? dp[i][j - 1] : 0);
                dp[i][j] = (from_up + from_left) % MOD;
            }
        }
    }

    cout << dp[n - 1][n - 1] << "\n";
    return 0;
}