jak znaleźć najdłuższą drogę zwiększania liczby w siatce? [duplicate] - algorytm

Zakładając, że mamy siatkę:

1 5 7
3 4 9
6 2 8

Rozwiązaniem byłoby: 1-3-4-5-7-9

Jak można by to rozwiązać?

Odpowiedzi:

Myślę, że ten problem można rozwiązać za pomocą rekurencyjnego dp. Wystarczy zapamiętać długość najdłuższej ścieżki uzyskanej przez rozpoczęcie od określonego punktu.

int dp[rows][cols]={0};
int dfs(int x , int y , int val)
{
if(dp[i][j] != 0 ) // already visited
return dp[i][j];
int lengthoflongestpath = 0;
Search in four directions in the grid for the element greater than val; // Say newx, newy,newval
lengthoflongestpath = max(lengthoflongestpath , dfs( newx , newy , newval));
lengthoflongestpath ++; // add that particular element to the path
dp[x][y] = lengthoflongestpath;
return dp[x][y];
}


int ans = 0;
for(i=0 to rows)
for(j=0 to cols)
if(dp[i][j] == 0) // unvisited
{
dp[i][j] = dfs(i,j,grid[i][j]);
ans = max(ans,dp[i][j]);
}
PRINT ans;

Zwraca długość najdłuższej ścieżki. Aby wydrukować dokładną ścieżkę, musimy użyć NASTĘPNEJ STRONY i zapisać następny element, który odpowiednio zwróci maksymalną „długość ścieżki”.

Złożoność: Rzędy * Cols

Edytuj: Jak wyszukiwać w 4 kierunkach.

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

for(int i=0; i<4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if(newx and newy lie inside the grid and newval > val)
dfs(newx,newy,newval);
}

Brzmi trywialnie, jeśli używasz rekurencyjnie, a struktura danych siatki zawiera flagę informującą, czy użyłeś liczby, czy nie.

List explore(Point start, Grid grid) {
List result = {}
for Point next in possible_choices(start, grid) {
grid.markUsed(next)
List proposed = explore(next, grid)
if(proposed.length > result.length) result = proposed;
else grid.markNotUsed(next)
}
result.prepend(start)

return result
}

Nie spędzałem zbyt wiele czasu na algorytmie, ale to byłoby coś podobnego ...