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

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


Дана матрица NxN, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K (клетку можно посещать несколько раз).

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>
 
using namespace std;
#define CLEAR_NEXTQ while (!nextQ.empty()) nextQ.pop();
#define MAX_SIZE 101
 
struct point
{
    int x; int y;
    point(){}
    point(int X, int Y)
    {
        x = X; y = Y;
    }
};
int n;
int steps;
int init[MAX_SIZE][MAX_SIZE];
int cur[MAX_SIZE][MAX_SIZE],prev[MAX_SIZE][MAX_SIZE];
queue<point> q,nextQ;
int moveX[4] = {0,1,0,-1};
int moveY[4] = {1,0,-1,0};
void input()
{
    cin>>n>>steps;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            scanf("%d",&init[i][j]);
}
bool correct(int x, int y)
{
    if (x<0 || y<0)
        return false;
    if (x>=n || y>=n)
        return false;
    return true;
}
void solve()
{
    q.push(point(0,0));
   
    for (int i=1;i<steps;i++)
    {
        while (!q.empty())
        {
            point p = q.front();
            q.pop();
            for (int i=0;i<4;i++)
            {
                int x = p.x + moveX[i];
                int y = p.y + moveY[i];
                if (correct(x,y))
                {
                    if (!cur[x][y])
                        nextQ.push(point(x,y));
                    cur[x][y] = max(cur[x][y],prev[p.x][p.y] + init[x][y]);
                }
            }
        }
        q = nextQ;
        CLEAR_NEXTQ
 
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
            {
                prev[i][j] = cur[i][j];
                cur[i][j] = 0;
            }
    }
   
    int res = prev[0][0];
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            res = max(res,prev[i][j]);
    cout<<res + init[0][0];
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    return 0;
}

         

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


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

Комментарии

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