Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vkditya0997's blog

By vkditya0997, history, 4 years ago, In English,

How to solve problem B ?

This problem looks similar to SPOJ-WATER

Someone please explain the approach to this problem?

Thank you!

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

4 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

My Java Code: