Grade 11 · Dynamic programmingCitește în română

Number of paths in a grid with obstacles

Original: Numărul de drumuri într-o grilă cu obstacole

O(n²)C++1767 lines2 examples

The idea

An n × m grid has free cells (0) and obstacles (1). How many paths lead from (1, 1) to (n, m) if we move only right or down and never enter obstacles? A free cell is reached from above or from the left, so nr[i][j] = nr[i-1][j] + nr[i][j-1], and on an obstacle nr[i][j] = 0. We start with nr[1][1] = 1 (if that cell is free). Unlike backtracking, we do not enumerate the paths, we only count them.

Original description (Romanian)

O grilă n × m are celule libere (0) și obstacole (1). Câte drumuri duc din (1, 1) în (n, m) dacă ne mișcăm doar la dreapta sau în jos și nu intrăm în obstacole? Într-o celulă liberă se ajunge de sus sau din stânga, deci nr[i][j] = nr[i-1][j] + nr[i][j-1], iar într-un obstacol nr[i][j] = 0. Pornim cu nr[1][1] = 1 (dacă celula e liberă). Spre deosebire de backtracking, nu enumerăm drumurile, ci doar le numărăm.

Complexity
O(n · m) time and memory
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

3 4
0 0 0 0
0 1 0 0
0 0 0 0

Expected output

4
Example 2

Input

2 2
0 1
1 0

Expected output

0

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

drumuri-in-grila-cu-obstacole.cpp
/*
 * Titlu: Numărul de drumuri într-o grilă cu obstacole
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: O grilă n × m are celule libere (0) și obstacole (1). Câte drumuri duc din
 *            (1, 1) în (n, m) dacă ne mișcăm doar la dreapta sau în jos și nu intrăm în
 *            obstacole? Într-o celulă liberă se ajunge de sus sau din stânga, deci
 *            nr[i][j] = nr[i-1][j] + nr[i][j-1], iar într-un obstacol nr[i][j] = 0.
 *            Pornim cu nr[1][1] = 1 (dacă celula e liberă). Spre deosebire de
 *            backtracking, nu enumerăm drumurile, ci doar le numărăm.
 * Complexitate: O(n · m) timp și memorie
 *
 * Exemplu
 * Intrare:
 * 3 4
 * 0 0 0 0
 * 0 1 0 0
 * 0 0 0 0
 * Ieșire: 4
 *
 * Exemplu
 * Intrare:
 * 2 2
 * 0 1
 * 1 0
 * Ieșire: 0
 */
#include <iostream>
using namespace std;

int a[105][105];
long long nr[105][105];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
            {
                nr[i][j] = 0;
            }
            else if (i == 1 && j == 1)
            {
                nr[i][j] = 1;
            }
            else
            {
                nr[i][j] = nr[i - 1][j] + nr[i][j - 1];
            }
        }
    }
    cout << nr[n][m] << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.