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.
