IaMaNanBord's blog

By IaMaNanBord, history, 2 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it