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

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

Problem

I used dfs but I'm getting incorrect answer. here's my code

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

»
10 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Scanning once like this is not enough. Do the whole thing again and again until no more updates can be made. It requires 2-3 iterations maximum to settle every cell.
Edit: I made that mistake. Though I don't know if you have the same problem, give it a try.

»
10 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +17 Проголосовать: не нравится

I approached it in a way similar to Bellman Ford Algorithm .

Take a matrix W and fill all the entries with infinity except the ones present in the border of the grid ie. i = 0 || i = (R - 1) || j = 0 || j = (C - 1) where i, j are the row index and column index respectively.

Now for each cell in the interior of the matrix water can come from 4 adjacent cells . We need to find the minimum of the incoming water from these cells and make this the new W[i][j] only if its greater than H[i][j]

For each cell with index i, j: min = min(W[x][y]) x, y adjacent to i, j and W[i][j] = max(min, H[i][j])

You need to run this relaxation for R * C times

Complexity : O(R2 C2)

My Java Code: Link