doxpox55's blog

Gym-100625J
By doxpox55, 4 years ago, In English

Hello, Good people. Hope you all are doing well. I am trying to solve the problem for a while but didnt come up any idea. Can anyone tell me how can I solve this problem?

Problem Link: https://vjudge.net/problem/Gym-100625J Thanks in advance. :)

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why downvote? If you cant help just ignore this.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thats because some people love to downvote newbie's blogs .. If the same blog was written by a person with rating 1900+ this wont happen .. That's the thing which I hate the most on codeforces.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The idea is considering the outside of the building in the grid. So you can use 0/1 bfs to find the shortest path from the outside to any cell (every door cost 1 and the empty space cost 0), and from any prisoner to every cell. Then, to find the answer you can iterate over all the cells. Take in mind that if your cell is a wall, skip this. If it's a door, the answer is the sum of the 3 distances — 2 (because your considering 3 times this cell and you only need to consider one) and if it's the empty cell is just the sum of the 3 distances (with 3 distances I mean, the distance from the outside and the two prisoners to every cell). I hope it helps.

→ Reply