Help with grid problem (dynamic programming)
Hey, long time reader, first time poster.
I'm working on a dynamic algorithm, and I've hit a roadblock in my thought process. Here's what I'm trying to do:
I'm given a X x Y rectangular grid in the form of an boolean array. The grid represents street intersections in a city. The goal is to walk to from South West corner (0,0) to the North East corner (X,Y) in the shortest amount of blocks. The problem is that any intersection labeled "true" is a dangerous intersection and must be avoided.
I've come up with 2 algorithms:
1. An O(XY) algorithm that finds a safe path, but not the shortest path. In just moves with Priorities (1. Up, 2. Right, 3. Left, 4. Down) and when it hits dead ends it remembers not to go back.
2. An O(X^2*Y^2) algorithm that tries every legal path and picks the best one.
What I am looking for is an O(XY) algorithm that finds the shortest safe path. I assume this would require dynamic programming. Here's what I've come up with so far:
- The minimum moves in a completely safe grid is X+Y.
- The minimum moves in any grid if X + Y + (number of needed down and left moves * 2), since all down and left move require an additional right or up move to regain progress.
So I'm trying to think of a way to find the necessary number of down + left moves, but do it in linear time. This is where I've hit a stumbling block. I've used 5 hours and about 60 sheets of scrap paper with little progress.
Anyone have any ideas? I'm not asking for code, just a way of going about the problem.