Tensor's blog

need help graph bfs problem?
By Tensor, 10 years ago, In English

any one can help me with this Problem from spoj. I have tried zillions time. once I used 3D bfs getting wrong answer then using 2D bfs getting between wrong answer and time limit.

2D bfs 3D bfs

thanks in advance!

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know if I'm wrong but my idea is that you should follow always an optimal path from the etrance to the treasure. Optimal path — a path with minimum number of traversed spikes. Then you should follow this same path on the way back to the entrance. If the number of spikes in the optimal path multiplied by 2 is higher than the number of allowed spike traversals then the answer is clearly that it's impossible to reach the treasure, otherwise it's possible.

A really straight-forward approach is to think of the maze as a graph and set the cost of edges that get you into a spike or out of a spike to 0.5. This way you can use a minimum cost path algorithm to find the optimal solution.

Another idea is to use a kind of smart flood-fill technique(BFS). First you should flood from the etrance all the cells without spikes, and mark them as visited. If you didn't reach the destination after this, push all the addiacent spike cells that are available from the flooded cells and add +1 to the global cost. Then do a flood-fill from the spiked cells, without visiting the cells you flooded on the previous path because it makes no sense to go to a spike cell then come back to a normal cell. Repeat this recursively until you reach the destination cell, or the global cost exceeds number_of_allowed_spikes/2.

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

    but if i had a case like this : 4 4 1 @@@@ ..s. ss.. x...

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

      4 4 1 @@@@ ..s. ss.. x...

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

      It looks like I misread the statement and thought there was only 1 entrance. I submited my solution with the second idea mentioned above and it was accepted, but it looks like it worked luckily for me, because in my code I was adding all the entraces to the initial queue, instead of just 1 like I said and wanted to.

      Now what's left for the algorithm I mentioned above is to prove that we must always follow the optimal way, even if we have multiple entrances. Let's call the optimal path A->X, where A is one of the initial entrances. Why do we follow this path? Because it leads us to a way with a minimal number of traversed spikes from an entrance to the treasure. Now let's say we reach the treasure X. Should we follow our way back to A or choose a path to another entrance? Let's say that there is better path from X to an entrance C, so let's call this path X->C. It follows that F(A->X)>F(X->C) where F is the function that gives us the number of minimal spikes traversed on a certain path. It's also obvious that F(@->X)=F(X->@) where @ is a random entrance.

      But if F(A->X)>F(X->C), then we shoud have chosen the path C->X from the beginning, so it contradicts that A->X is an optimal path. (it actually comes to the fact that there is a more optimal path than the optimal path, so it leads to an absurd statement). This way we proved that we always need to follow the optimal path from the start to the finish, and from the finish to the start.

      Here is my code that worked: http://ideone.com/x7MYPB If you want to do it yourself, then you should better not open it.

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

        thank you very much :-)

        i'll try to implement it myself first :)

        → Reply