axelabhi's blog

a little help with uva 11624 Fire!
By axelabhi, history, 8 years ago, In English

i was trying to do this question using a single bfs. I push the location of joey and all the fires in the queue and if joey reaches the corner i will get my ans. I think it is correct because if joey has moved through a path then there is no point in fire following after him . I tried all the test case in UDebug and it works fine on them but I am getting wrong answer on Uva judge. here is the link to my code https://ideone.com/qLt4eF any help would be appreciated thank you.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

First of all take care of the line that fire also spreads in all directions. This means that from initial positions of fire, it will move to all it's adjacent positions and further. Also check the bfs part of your code. Here is the AC solution : http://paste.ubuntu.com/24224605/

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

    well what you did is you set the fire first and then store the time at each cell then you run another bfs for joey to check where he can go and whether he can find a solution or not. what i am doing is i spread the fire after each instant of time and then move joey to position he can occupy. i mark the positions fire has moved to it's neighbours as visited and the positions joey has visited. what i am doing different from your algorithm is i am not spreading fire to a location if joey has already been there because if joey has been there then any further path that fire may block joey would reach it before the fire and hence can safely pass.This logic seems fine to me but well i am getting WA so if you could give me flaw in this logic or point out any other mistake i would be grateful thank you.

    → Reply