×

# Dynamic Programming

 0 Hey how to solve this problem? Thanks in Advance asked 27 Mar '18, 00:08 94●4 accept rate: 0% 1 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. (27 Mar '18, 22:14) meooow ♦6★ Noted! @meooow (31 Mar '18, 22:21)

 0 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. answered 27 Mar '18, 13:12 1●1 accept rate: 0%
 0 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 . answered 27 Mar '18, 16:32 240●1●10 accept rate: 13%
 0 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]..!! answered 01 Apr '18, 02:46 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,095

question asked: 27 Mar '18, 00:08

question was seen: 479 times

last updated: 01 Apr '18, 02:46