Блог пользователя IaMaNanBord

Автор IaMaNanBord, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$.

  1. If $$$n > 2$$$, then there are at most $$$n-2$$$ horizontal candidate lines: $$$x = c$$$, where $$$2 \leq c \leq n-1$$$.
  2. If $$$m > 2$$$, then there are at most $$$m-2$$$ vertical candidate lines: $$$y = c$$$, where $$$2 \leq c \leq m-1$$$.
  3. There are at most $$$n+m-1$$$ diagonal candidate lines: $$$x+y = c$$$, where $$$2 \leq c \leq 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:

  1. $$$x+y = 2$$$, and the blocked cell is $$$(1,1)$$$
  2. $$$x+y = 4$$$, and the blocked cell is $$$(2,2)$$$
  3. $$$x+y = 5$$$, and the blocked cell is $$$(2,3)$$$.

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)$$$.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Do you have a link for the problem?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • there exists a path from $$$(1, 1)$$$ to $$$u$$$,
    • there exists a path from $$$v$$$ to $$$(n, m)$$$, and
    • the edge $$$(u, v)$$$ crosses over $$$x$$$ in the topological order, i.e., $$$u$$$ occurs before $$$x$$$ and $$$x$$$ occurs before $$$v$$$ in the topological order.

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.