If you want to make money online : Register now

[Answers] Find path to point and avoid bear

, , No Comments
Problem Detail: 

I'm so far a self taught programmer who's mostly been working on simple web and app development. But now my teacher wants me to enter a school competition in programming. Of course the competition is based on problem solving and such, areas I'm guessing counts as computer science. Even though I don't have much experience with this kind of problem solving I have been getting along quite well through the exercise problems.

Unfortunately I'm now completely stuck on one of the harder exercises and I could really use some help.

The problem is as follows: You're in a cave which can be represented as a grid which size is defined by w and h, the cave also has walls inside it. Your goal is to get to the exit without the bear, who's also in the cave, reaching you. You are able to move only one step at a time and you have to move every tick. The bear is able to two steps at a time to reach you.

But the bear is a bit stupid. First it moves horizontally until it's in the same column as you and then it continues by moving vertically until it reaches you. The bear is not aware of the walls and simply walks right into them.

The output should be a sequence of movements defined as U: up, L: left, D: down and R: right.

I'm currently programming in python but I'm not to interested in a real implementation. I would much rather have directions on how to think and reason to solve these kinds of problems.

I have a few test-cases if needed.

Asked By : Fabian Lindfors

Answered By : shaunTheSheep

The obvious approach for typical path finding problems such as this one is that you store the state of the problem in a data structure, usually a lookup array.

In this case, you will have 2 variables, one for your position and one for the bear's position. Since the bear's movement is dependent on other factor, you can do a top down search approach and recursively check your options.

The running time will be polynomial to the size of the grid which will be $O((wh)^2)$. There might be other optimizations, but this will be the general direction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31864

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback