Блог пользователя 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
  • Проголосовать: не нравится