-----------------------------------

Cinjection

Tue Feb 12, 2008 6:54 pm


Dynamic Programming Problem.

-----------------------------------

Today, I wrote the Dwite contest and tried to get #4 (http://dwite.org/questions/train_ride.html) complete, which I understand is a dynamic programming type problem. I've never written a solution to such a problem, but I gave it a go. 

Here is what I got up to, in terms of a definition:

Let A[r][c] = The grid
Let D[r][c] = Least number of steps between [r][c] and 'S' (This is initialized to 999)
Let M(r, c) return the least number of steps to reach r,c

My recursive definition was:

M(r, c):
if (r || c are out of bounds) return 1000
if ( D[r][c] != 999) return D[r][c]
if ( A[r][c] = 'x' || ' ' ) return 1000;
if ( A[r][c] = 'S' ) return 0;
else:
return Min( M(r+1, c), M(r, c+1), M(r+1,c+1), M(r-1, c), M(r, c-1), M(r-1,c-1), M(r+1, c-1), M(r-1, c+1)  ) + 1;

And I Fill the array (D) as such:
for (int i(0); i < 5; i++)
{
    for(int j(0); j