Блог пользователя none__none

Автор none__none, история, 5 лет назад, По-английски

There is a NxM 2D matrix given .Each Cell contains a value.

We need to find the smallest number that can be reached from a cell but we are allowed to

go from one cell to its adjacent cell which share an edge and we can go

from one cell to another only if another cell value is strictly less than the

current cell. And we have to find this value for each cell.

e.g-

A=[[2 4 3 1] [2 1 5 0]]

result for the above is:

res=[[2 0 0 0] [1 1 0 0]]

0<=A[i]<=1000000 1<= N,M<=1000

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

For the transaction rule, we can deduce that the graph does not contain cycles so we can get a simple solution with dp. For evry cell just try to get the min value from his adjacencies. Complexity O(N * M). My solution :

Code

Sorry for poor english.