Given a matrix of size N X M consisting of ‘#’, ‘.’ and ‘*’. ‘#’ means blocked path, ‘.’ means walkable path and ‘*’ means points that you have to collect. Now consider you are at the top left of the matrix. You have to reach the bottom right of the matrix and come back to the top left. When you are moving top left to bottom right, you are allowed to walk right or down. And when you are moving the bottom right to top left, you are allowed to walk left or up. The task is to find the maximum points you can grab during your whole journey. Points once taken will be converted into ‘.’ i.e walkable path.
Input : N = 3, M = 4 **** .##. .##. **** Output : 8 Input : N = 9, M = 7 *........ .....**#. ..**...#* ..####*#. .*.#*.*#. ...#**... *........ Output : 7
If you consider two paths – one from (0, 0) to (N – 1, M – 1) and another from (N – 1, M – 1) to (0, 0) and collect maximum * in each path. You might end up with wrong answer. If you add the answer of both the paths independently, you will be calculating the intersecting points once again while backtracking. Essentially, ending up with the same path. Even if you keep a visited array, marking every * on the first path, you will still not end up with the correct answer.
Consider the following example:
If we consider as two independent path, then
total * collected is 7.
Whereas the maximum points collected can be 8 by following paths.
There are 4 * on each path. Hence, total = 8.
Thus we see that the optimal solution is not the sum of optimal solutions of both the path independently. The optimal answer for one does not ensure an optimal answer.
So, we will have to calculate both the paths simultaneously. This is needed because the answer for path 2 depends on the route chosen by path 1. Simultaneous calculations can be done by considering two paths from (0, 0) to (N-1, M-1) and making four decisions at each position (two for each).
So instead of two traveling one path from top left to the bottom right and other from the bottom right to top left, we will travel two paths from (0, 0) to (N-1, M-1) simultaneously, so at each step, we take one step for both paths. So our state will consist of (x1, y1, x2, y2) where (x1, y1) is the position of the first path and (x2, y2) is the position of the second tourist in the grid.
Points to notice:
1. At each step either step can move right or down, so we have 4 choices for movement(2 choices for each path).
2. If both paths are on the same cell (x1 == x2 and y1 == y2) then we can add only 1 to result if that cell has *.
3. We can reduce the complexity by reducing the state dimension from 4 to 3. If we know the position of first path (x1, y1) the x coordinate of second path x2, then we must have x1 + y1 = x2 + y2 since both path cover the same distance in the same amount of time. So y2 = x1 + y1 – x2 and our state depends only on (x1, y1, x2).
Below is C++ implementation of this approach:
Time Complexity: O(N^3)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org