So, recently I came across a problem related to finding min cost. The problem statement is as follows -
You are given a grid with n rows and m columns and each cell is either empty (.) or blocked (#). Now you can block only one cell in the grid such that there is no path left from $$$(1,1)$$$ to $$$(n,m)$$$. A path can contain only right or (and) down moves.
Cost for blocking any cell $$$(i,j)$$$ is given as $$$cost(i,j)$$$. You need to find the minimum cost for achieving the task.
The expected solution should take $$$O(n * m)$$$ time.
Example
Note
Please provide some hints for solving this problem.
Note that there are at most three different slopes for candidate lines in the grid such that if exactly one cell is empty and all other calls on such line if exist are blocked, then blocking this cell will block all paths between cell $$$(1,1)$$$ and cell $$$(n,m)$$$.
If either $$$n = 1$$$ or $$$m = 1$$$, then the solution is the minimum cost of all cells.
In the given example, there are three diagonal candidate lines:
The vertical line $$$y = 2$$$ is not candidate, as it has two empty cells.
A simple way to find candidate lines is to have a counter for each horizontal, vertical and diagonal line that stores the number of empty cells on such line; all initialized to zeros. The corresponding counters for row $$$r$$$, column $$$c$$$ and diagonal $$$r+c$$$ should incremented if the scanned cell $$$(r,c)$$$ is empty.
The time complexity of checking all possible candidate lines should be $$$O(n * m)$$$.
Do you have a link for the problem?
Sorry but I don't have the link for the problem.
Suppose $$$A$$$ is the set of all valid paths from $$$(1,1)$$$ to $$$(n,m)$$$, and $$$B$$$ is the set of all cells $$$(x,y)$$$ such that if the cell $$$(x,y)$$$ is blocked, there is no path from $$$(1,1)$$$ from $$$(n,m)$$$.
Let's take an arbitrary cell $$$(i,j)$$$. Now for $$$(i,j)$$$ to be present in $$$B$$$, it should be included in all paths of $$$A$$$. If $$$a[i][j]$$$ is the number of ways to reach $$$(i,j)$$$ from $$$(1,1)$$$ and $$$b[i][j]$$$ is the number of ways to reach $$$(n,m)$$$ from $$$(i,j)$$$, $$$(i,j)$$$ would be included in all paths of $$$A$$$ iff $$$a[i][j]*b[i][j] = a[n][m]$$$. Since $$$a[i][j]$$$ and $$$b[i][j]$$$ can be quite large, you can check whether $$$a[i][j]*b[i][j] = a[n][m]$$$ by hashing. You can calculate $$$b[i][j]$$$ by reversing all the edges and starting from $$$(n,m)$$$.
Similar problem
Yeah, actually I also thought of this approach but $$$a[i][j]$$$ and $$$b[i][j]$$$ could have factorial growth and I didn't know any way to handle this, so, discarded the idea.
I would be thankful to you if you could provide some resources related to such hashing technique.
My submission for the linked problem in my previous comment
I stored $$$a[i][j]$$$ modulo $$$M$$$ and $$$b[i][j]$$$ modulo $$$M$$$, where $$$M = 998244353$$$. I hope it helps.
Using a fixed value of $$$M$$$ leaves you vulnerable to getting hacked. It's typical to use one or two (runtime-generated) random primes from $$$[10^9, \ldots , 2\cdot 10^9]$$$ to avoid that problem.
Really interesting idea. Thanks a lot.
I think instead of counting the number of ways, we can also do a topological sort of the graph and then for each vertex $$$x$$$ for which there exists a path from $$$(1, 1)$$$ to $$$x$$$ and from $$$x$$$ to $$$(n, m)$$$, check if there is at least one edge $$$(u, v)$$$ such that
If there exists such an edge, blocking this vertex would still leave a path from $$$(1, 1)$$$ to $$$(n, m)$$$. Otherwise, all paths from $$$(1, 1)$$$ to $$$(n, m)$$$ go through this vertex and blocking it would achieve the purpose.
We can check this for each valid vertex by iterating over the topological order and maintaining the rightmost vertex reachable by a valid edge till now.
Another similar problem.
you can use prim algorithm to find mst, to block the path.
there are 4 ways to block the path.
1] up — down
2] down — right
3] left- up
4] left — right
(by surface i mean boundary of the grid) now for each case you can push cells connected to one surface to component , and another surface to another component , and run mst to get minimum cost. to join this two components.
minimum of all the 4 cases will be your answer.
runtime complexity will n * m log(n * m) , using priority_queue, not sure but you can avoid priority_queue to avoid extra log factor.