Решение задачи Минимальный путь в таблице с Acmp

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


В прямоугольной таблице N×M (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Код

#include <bits/stdc++.h>
 
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)
            cin >> a[i][j];
       if(m == 1 && n == 1){
        cout << a[0][0];
        return 0;
    }
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            b[i][j] = 0;
    b[m - 1][n - 1] = a[m - 1][n - 1];
    for(int i = m - 2; i >= 0; --i)
        b[i][n - 1] = b[i + 1][n - 1] + a[i][n - 1];
 
    for(int i = n - 2; i >= 0; --i)
        b[m - 1][i] = b[m - 1][i + 1] + a[m - 1][i];
    for(int i = m - 2; i >= 0; --i){
        for(int j = n - 2; j >= 0; --j){
            b[i][j] = min(b[i + 1][j], b[i][j + 1]) + a[i][j];
        }
    }
 
    int i = 0, j = 0,s = a[0][0];
    while(i != m - 1 && j != n - 1){
        if(b[i + 1][j] > b[i][j + 1])
            ++j;
        else
            ++i;
        s+=a[i][j];
 
    }
    if(i == m - 1 && j != n - 1)
        for(int h = j + 1; h < n - 1; ++h)
            s+=a[i][h];
    if(j == n - 1 && i != m - 1)
        for(int h = i + 1; h < m - 1; ++h)
            s+=a[h][j];
    s+=a[m - 1][n - 1];
    cout << s;
    return 0;
}

         

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




Комментарии

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