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.

Eg — Suppose we are given a grid ~~~~~ ..# ... ~~~~~ and cost is given as ~~~~~ 3 1 2 4 2 3 ~~~~~

Then possible choices for blocking are (1,1), (2,2) and (2,3). Thus min cost will be 2 for blocking (2,2).

But if we block (1,2) then there would be a path from (1,1) to (2,3). So it is an invalid choice.

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.