spontaneously's blog

Google APAC 2017 round A problem B Rain
By spontaneously, history, 10 years ago, In English

Problem

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

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

Comments Comments (6)
| Write comment?
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it +17 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

Complexity : O(R2 C2)

My Java Code: Link

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you explain, how does this logic work ?

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Bro....your code is really very clean and nice :) However it is more than enough to run it for 2*max(R,C) instead of (R*C) as it will take at most 2*max(R,C) for any update at any cell to reach any other cell in array W.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +1 Vote: I do not like it

      You mean to say that the longest path in the grid is 2*max(R,C) . Shouldn't it be (R + C) ?

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Wow Bro....That is really a cool observation. That what i meant. Its enough to have (R+C) repetitions over the matrix W :)

        → Reply