lalalalaaa...'s blog

CSES Graphs- Monsters (Help needed)
By lalalalaaa..., history, 4 years ago, In English

I have started solving some problems related to graphs and most of the times i am not able to pass the testcases, either it is TLE or WA. I was solving MONSTERS question from cses Problem Link and was unable to figure to out why some testcases gave TLE.

What i have done-

Applied bfs and stored the min distance between each cell and the monster (M) cell. Applied bfs for A and check whether there was a cell which was having less distance/ or more closer to A than any other M cell. And then checked whether it can reach to any border cell.

Link to My Code

It will be very helpful if anyone can let me know where i am going wrong.

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can check this, I have used bfs
CODE_LINK

CODE
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have applied multisource bfs only, but 4 testcases were giving TLE. My Code Sorry for the late reply

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

      I have not looked through your code thoroughly, I can see problems in your functions, it is never a good idea to pass vector to a function by value, this would copy the entire vector, rather you should pass by reference.

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

Hi there,

Sorry haven't thought about the exact error in your code but I will state why I was getting WA and TLE

The reason for TLE was the case when your character is already at a border cell and the reason for WA was due to >= instead of just > when comparing distance during bfs from your cell.

→ Reply