Пройдите по сетке с максимально возможным весом и без повторения пути - PullRequest
Новая
       19

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

0 голосов
/ 08 января 2019

Учитывая, что сетка NxN с каждой ячейкой имеет некоторый вес, связанный с ней, и есть 2M ячеек в сетке, которые помечены, и нам нужно пройти (начать с отмеченной ячейки и закончить в отмеченной ячейке) таким образом что все пути должны быть уникальными (начальная и конечная точки тоже), а также сумма весов всех ячеек во всех путях настолько велика, насколько это возможно.

Входной сигнал: -

Допустим, N = 4, M = 2

(1 1), (2 2), (3 3), (4 4) {отмеченные ячейки в сетке}

1 -1 -1 -1

1 1 1 1

1 1 1 1

-1 -1 -1 1 {сетка с весами}

Вывод: -

сначала нам нужно вывести количество посещенных нами клеток, а затем путь

5 1 1 2 1 3 1 3 2 3 3 {5 посещенных ячеек и (1,1) начало и (3,3) окончание}

5 4 4 3 4 2 4 2 3 2 2 {аналогично последнему}

, поэтому мы посетили все отмеченные ячейки, и общий вес (сумма весов в 1-м пути + 2-й путь) максимально возможен.

Моя идея -:

Я понял (если не так, пожалуйста, поправьте меня), что это комбинация нескольких проблем с сеткой + DP

(1). найти путь в сетке с максимальным весом.

* +1032 * (2). достижение данной клетки, начиная с данной клетки.

Теперь над двумя стандартными проблемами DP + Grid, и я решил каждую из них отдельно 

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
int main()
{
    int X,Y; //X:number of rows, Y: number of columns
    X = Y = 10; //assuming 10X10 matrix
    int Cost[X][Y];

    F(i,0,X-1)
    {
        F(j,0,Y-1)
        {
            //Take input the cost of visiting cell (i,j)
            cin>>Cost[i][j];
        }
    }

    int MinCost[X][Y]; //declare the minCost matrix

    MinCost[0][0] = Cost[0][0];

    // initialize first row of MinCost matrix
    F(j,1,Y-1)
        MinCost[0][j] = MinCost[0][j-1] + Cost[0][j];

    //Initialize first column of MinCost Matrix
    F(i,1,X-1)
        MinCost[i][0] = MinCost[i-1][0] + Cost[i][0];

    //This bottom-up approach ensures that all the sub-problems needed
    // have already been calculated.
    F(i,1,X-1)

и аналогичным образом я решил поиск пути, но потом понял, что это проблема 2 источников, мы можем начать с 2 указанных ячеек (1 начальная отмеченная ячейка и 1 конечная отмеченная ячейка), но там мне нужно предоставить среднюю ячейку, где они должны встретиться .

Так можете ли вы предоставить некоторый намек или псевдо-код, как объединить все эти проблемы ??

...