The classic problem of counting distinct paths in a rectangular grid where movement is restricted to right and down steps can be modeled as a binary tree structure, but such an approach leads to exponential time complexity. A more efficient solution uses dynamic programming with a two-dimensional state table.

Grid without Obstacles

Given an m x n grid, define ways[r][c] as the number of unique routes from the top-left corner (0,0) to cell (r,c). The recurrence relies on the fact that the only way to reach (r,c) is from the cell directly above or from the left:

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

For the first row and first column, only one straight-line path exists, so these cells are initialized to 1. The entire table is then filled row by row. The final answer resides at ways[m-1][n-1].

int countPaths(int rows, int cols) {
    vector<vector<int>> ways(rows, vector<int>(cols, 0));
    for (int r = 0; r < rows; ++r) ways[r][0] = 1;
    for (int c = 0; c < cols; ++c) ways[0][c] = 1;
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            ways[r][c] = ways[r-1][c] + ways[r][c-1];
        }
    }
    return ways[rows-1][cols-1];
}

Grid with Obstacles

When some cells are blocked, they cannot be used in any path. The obstacle matrix grid contains 1 for blocked cells and 0 for free cells. The recurrence remains the same, but it applies only when the current cell is free; otherwise, the number of routes to that cell stays 0.

Initialization also changes. If a cell in the first row or first column is blocked, all cells beyond it in that row or column become unreachable and must remain 0.

int countPathsWithObstacles(vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    
    if (grid[0][0] == 1 || grid[rows-1][cols-1] == 1) return 0;

    vector<vector<int>> ways(rows, vector<int>(cols, 0));
    for (int r = 0; r < rows && grid[r][0] == 0; ++r) ways[r][0] = 1;
    for (int c = 0; c < cols && grid[0][c] == 0; ++c) ways[0][c] = 1;

    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            if (grid[r][c] == 1) continue;
            ways[r][c] = ways[r-1][c] + ways[r][c-1];
        }
    }
    return ways[rows-1][cols-1];
}

The traversal order (top-to-bottom, left-to-right) ensures that the reuqired previous states have already been computed. For large grids, space can be optimized to a single row of size n, but the two-dimensional formulation clearly reflects the problem's structure.