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

DemonStar's blog

By DemonStar, history, 5 weeks ago, In English,

Monsters

Link to the problem statement

How to solve this problem.

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Looks like multi-source BFS would help.
Run 2 BFS simultaneosuly, one for hero and other for all monsters combined. Delete nodes in hero's graph whenever all monsters take an extra step. If hero's BFS still finds boundary , then he wins.
I'll update once I have tried.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using similar approach as mentioned above

    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have done similar as you said but in cses submission in two testcase it shows UNKNOWN but IDE gives correct answer and in one testcase it gives TLE can you please help me out.my code

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think reason for TLE might be ans=perent[x][y]+ans;

        Try using += and reversing the string

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting the Way I approached it was I enqueued all the monsters positions and did bfs on those and kept the closest distance of any coordinate in the grid in a matrix. Then I just did normal bfs from the start position but had to add a condition that If I am at a cell (i, j) going to a cell(x, y) the distance I travel to (i, j) has to be strictly less than the closest distance from the monsters to (x, y). an interesting problem I saw similiar to this was IOI 2009 Mecho, which was similiar but added another part to the problem my code for the problem is here do note that visited1 is the closest distance to a square from a monster and visited is the closest square from the person https://pastebin.com/GBDJxiFm

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well, in the end it is the same. All fields are divided into two groups: Fields monsters reach first, and fields hero reach first. We need to find a path using only the fields of the hero group.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks, I got it.