1. Идея

Нужно посчитать количество путей из левой верхней клетки в правую нижнюю, если можно ходить только вправо и вниз, а некоторые клетки запрещены.

Классическая идея здесь — динамическое программирование.

Пусть количество способов попасть в клетку зависит только от двух соседних клеток:

• сверху;
• слева.

Почему так? Потому что в клетку можно прийти только одним из этих двух ходов.

Если клетка занята, попасть в неё нельзя, значит число путей в неё равно 0.

2. Наблюдения

Наблюдение 1

Если клетка свободна, то

ways[i][j] = ways[i - 1][j] + ways[i][j - 1]

То есть число путей в клетку равно сумме:

• путей в клетку сверху,
• путей в клетку слева.

Наблюдение 2

Если клетка занята, то

ways[i][j] = 0

независимо от соседей.

Наблюдение 3

Для стартовой клетки есть особый случай:

• если она свободна, то в неё можно попасть ровно одним способом — уже находиться в ней;
• если она занята, ответ сразу будет 0.

В эталонном решении этот случай уже аккуратно учтён в общем проходе по таблице.

Наблюдение 4

Хранить всю таблицу m x n не обязательно.

Чтобы посчитать текущую строку, достаточно знать:

• значения из предыдущей строки;
• уже посчитанные значения в текущей строке.

Поэтому можно хранить только одномерный массив dp длины n.

3. Алгоритм

Будем обрабатывать сетку построчно слева направо.

dp[j] будет означать текущее количество путей в клетку текущей строки и столбца j.

До обновления:

• dp[j] — это число путей из клетки сверху;
• dp[j - 1] — это уже обновлённое число путей из клетки слева.

Шаги алгоритма

1. Считать m и n.
2. Создать массив dp длины n, заполненный нулями.
3. Для каждой строки i:
   • для каждого столбца j считать значение клетки;
   • если клетка занята (1), записать dp[j] = 0;
   • иначе:
     • если i == 0 и j == 0, то dp[j] = 1;
     • иначе:
       • from_up = dp[j]
       • from_left = dp[j - 1], если j > 0, иначе 0
       • dp[j] = (from_up + from_left) % 1000000007
4. После обработки всей сетки ответ находится в dp[n - 1].

4. Почему это работает

Докажем, что алгоритм действительно считает количество маршрутов правильно.

Рассмотрим произвольную свободную клетку.

В неё можно попасть только двумя способами:

• из клетки сверху;
• из клетки слева.

Других допустимых ходов нет, потому что робот умеет двигаться только вправо и вниз.

Значит, все пути в текущую клетку разбиваются на две непересекающиеся группы:

• пути, которые заканчиваются переходом сверху;
• пути, которые заканчиваются переходом слева.

Количество путей в текущую клетку равно сумме количеств путей в эти две соседние клетки.

Если клетка занята, через неё нельзя пройти вообще, значит число путей равно 0.

Теперь разберём, почему одномерный массив работает корректно.

При обработке клетки (i, j):

• dp[j] ещё хранит число путей в клетку (i - 1, j), то есть сверху;
• dp[j - 1] уже обновлён и хранит число путей в клетку (i, j - 1), то есть слева.

Именно эти два значения и нужны для перехода.

Стартовая клетка (0, 0) свободна — тогда путь ровно один. Если она занята, на шаге обработки препятствия значение станет 0, и это правильно.

Значит, после обработки всех клеток dp[n - 1] содержит точное число маршрутов в правую нижнюю клетку.

5. Сложность

Пусть в сетке m строк и n столбцов.

Время

Мы один раз обрабатываем каждую клетку:

• O(m * n)

Память

Используется только массив длины n:

• O(n)

Это важно, потому что при ограничениях до 1000 x 1000 такое решение работает эффективно.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    int m, n;
    cin >> m >> n;

    vector<long long> dp(n, 0);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int cell;
            cin >> cell;

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

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

7. Код на Python 3

MOD = 1000000007

m, n = map(int, input().split())
dp = [0] * n

for i in range(m):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] == 1:
            dp[j] = 0
        else:
            if i == 0 and j == 0:
                dp[j] = 1
            else:
                from_up = dp[j]
                from_left = dp[j - 1] if j > 0 else 0
                dp[j] = (from_up + from_left) % MOD

print(dp[n - 1])