# 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, 2014 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. :) Oct 22, 2014 at 12:45

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.