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

Gym-100625J
Автор doxpox55, 4 года назад, По-английски

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. :)

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

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

Why downvote? If you cant help just ignore this.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить