# Find path to point and avoid bear

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.

• Welcome to CS.SE! What approaches have you considered? What have you tried? Have you tried anything, to see if it works? What kind of thinking or reasoning have you done? On this site, we expect you to make a serious effort on your own before asking, and tell us in the question what kinds of approaches you considered and what specific aspects you are having difficulty with. Can you edit your question to include that information, please? – D.W. Oct 12 '14 at 23:44
• @D.W. Thanks for the introduction, very useful. I'm sorry that I haven't answered sooner but I've been kind of busy. I'll think about what you noted next time. :) – Fabian Lindfors Oct 22 '14 at 12:45

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.

• Sorry for such a late answer, with the help of some friends and our teacher we managed to solve the problem. I believe your solution was close to ours and probably much more efficient, so I marked it as correct. Thanks! :) – Fabian Lindfors Oct 22 '14 at 12:48