Dynamic Programming

general
1

Hey how to solve this problem? Thanks in Advance

1 Like
2

  1. Take a linear DP array which you’ll use as a table.

  2. Instead of taking a boolean visited array, take an integer array and store a unique number for each DFS search.

  3. Use this index to refer to DP array whenever you encounter a query which is already visited.

    if(!vis[a][b]) {
    ++idx;
    ans = dfs(a, b);
    dp[idx] = ans;
    }
    printf("%d\n", dp[ vis[a][b] ]);

You can also use a Union-Find Data Structure.

3

Hi,

The problem asks u to find the number of pictures(maximum) he can see for the given k starting positions.

So for now leave the k queries and solve the problem.

Approach:1) start iterating the museum and whenever u encounter an empty cell perform dfs if it is not visited and count the pictures he can see and the answer will be the same for all the empty cells we get in the path of dfs.

void dfs(int a,int b)

{

path.push_back(make_pair(a,b));

checker(a-1,b);

checker(a+1,b);

checker(a,b-1);

checker(a,b+1);

}

Now in checker function we add the answer of the pictures.

void checker(int a,int b)
{

if (visited[a][b])
return;

if (museum[a][b]=='*')
	++C;

else
  dfs(a,b);

}

Here C is the maximum pictures he can see and it is same for all the empty cells in that component.

Now we have the answer for all the cells as starting point so for each query just output the answer .

4

U need to simply apply dfs from the starting point given in the query if u dont have its answer precalculated…now the recurrence for dp could be like

dp[x][y]+=1 …if adjacent child is ‘*’ or
dp[x][y]+=dp[child_x][child_y]…where arr[child_x][child_y]=’.’…

“Now answer for all the nodes visited in dfs will be equal to dp[x][y]”,this is because if u can visit child_x and child_y from x and y and see dp[x][y] pictures then you can also see dp[x][y] pictures if you start your journey from child_x and child_y…

To implement this simply take a vector of pair…push all the nodes visited in this vector and do something like this…
for(auto it:v)
{
dp[it.first][it.second]=dp[x][y];
}
Now print the value of dp[x][y]…!!

5

I think it would be appropriate to put the full name of the problem in the question title. It may help someone searching for it in the future.

1 Like
6

Noted! @meooow