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

Tough heap problem
Автор aakarshmadhavan, история, 6 лет назад, По-английски

Can someone give some hints? I have absolutely no clue how heap or anything else fits into this? Thank you!

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

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

I'm not completely sure, but this approach should work — binary search on the final answer.

Assume the answer is <=x. Now, mark arr[i][j]=1 if grid[i][j]<=x and 0 otherwise. Build connected components of 1's in arr. Now the answer is <=x if both the source and destination are 1 and lie in the same connected component of arr. Binary search on x to get your answer.

→ Ответить