Решение задачи "Маршрут" с Меньшиков

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


В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Код

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> res;
vector<vector<int> > mas,sum;
int n;
void input()
{
    cin>>n;
    mas = vector<vector<int> >(n,vector<int>(n,0));
    sum = vector<vector<int> >(n,vector<int>(n,0));
    res = vector<string>(n,string(n,'-'));
    char c;
    for (int i=0;i<n;i++){
        cin.get(c);
        for (int j=0;j<n;j++){
            cin.get(c);
            mas[i][j] = c - '0';
        }
    }
}
void solve()
{
    // формирование массива sum
    sum[0][0] = mas[0][0];
    for (int i=1;i<n;i++)
    {
        sum[0][i] = mas[0][i] + sum[0][i-1]; res[0][i] = 'l';
        sum[i][0] = mas[i][0] + sum[i-1][0]; res[i][0] = 'u';
    }
    res[0][0] = 'i';
    for (int i=1;i<n;i++)
        for (int j=1;j<n;j++)
        {
            // рекуррентная формула:
            // sum[i][j] = mas[i][j] + min(sum[i-1][j],sum[i][j-1]);
            sum [i][j] = mas[i][j];
            if (sum[i-1][j]<sum[i][j-1])
            {
                sum[i][j]+=sum[i-1][j];
                res[i][j] = 'u';
            }
            else
            {
                sum[i][j]+=sum[i][j-1];
                res[i][j] = 'l';
            }
        }
 
    // формирование ответа
    int x = n-1, y = n-1;
    bool isEnd = false;
    do
    {
        int X = x,Y = y;
        if (res[x][y] == 'u')   x--;
        else if (res[x][y] == 'l') y--;
        else if (res[x][y] == 'i') isEnd = true;
        res[X][Y] = '#';
    }
    while (!isEnd);
}
void output()
{
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
            if (res[i][j] != '#')   cout<<'-';
            else    cout<<'#';
        cout<<endl;
    }
}
int main()
{
    input();
    solve();
    output();
    return 0;
}
 

         

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


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

Комментарии

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