Min cost for path blocking

Правка en2, от IaMaNanBord, 2021-11-10 08:34:07

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.

Example

The expected solution should take $$$O(n * m)$$$ time.

Note :

  • I have tried finding some relationship between blocked and unblocked states for cell $$$(i,j)$$$, $$$(i-1,j)$$$ and $$$(i,j-1)$$$ but couldn't find any.
  • I think finding min cost at articulation points will do the job but I can't find any resource for articulation points in directed graph.

Please provide some hints for solving this problem.

Теги dp, graphs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский IaMaNanBord 2021-11-10 09:02:34 136 Tiny change: 'spoiler>\nNote : \n\n\nPlease' -> 'spoiler>\n\nPlease'
en3 Английский IaMaNanBord 2021-11-10 08:36:42 2
en2 Английский IaMaNanBord 2021-11-10 08:34:07 46 Tiny change: ' choice.\n\n\n</spoile' -> ' choice.\n</spoile' (published)
en1 Английский IaMaNanBord 2021-11-10 08:30:18 1242 Initial revision (saved to drafts)