Решение задачи Только вправо или вниз с Acmp

Без пояснения   Просмотров: 68


Игровое поле N×M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего.

Код

#include <iostream>
 
using namespace std;
 
int main()
{
    int m,n;
    cin >> m >> n;
    int a[m][n];
    int b[m][n];
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j)
            b[i][j] = 0;
    }
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j)
            cin >> a[i][j];
    }
    b[m - 1][n - 1] = 1;
    for(int i = n - 2; i >= 0; --i){
        if(a[m - 1][i] <= n - 1 - i && b[m - 1][i + a[m - 1][i]] != 0)
            b[m - 1][i] = 1;
    }
    for(int i = m - 2; i >= 0; --i)
        if(a[i][n - 1] <= m - 1 - i && b[i + a[i][n - 1]][n - 1] != 0)
            b[i][n - 1] = 1;
 
    for(int i = m - 2; i >= 0; --i){
        for(int j = n - 2; j >= 0; --j){
            if(a[i][j] <= m - 1 - i && b[i + a[i][j]][j] && a[i][j] <= n - 1 - j && b[i][j + a[i][j]])
                    b[i][j] = b[i][j + a[i][j]] + b[i + a[i][j]][j];
            else
                if(a[i][j] <= m - 1 - i && b[i + a[i][j]][j])
                    b[i][j] = b[i + a[i][j]][j];
            else
                if(a[i][j] <= n - 1 - j && b[i][j + a[i][j]])
                    b[i][j] = b[i][j + a[i][j]];
 
        }
    }
    cout << b[0][0];
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться