This problem is actually a searching or flood-fill problem. The goal is to touch all the squares in a matrix to see how 'far away' each of them is from the origin. Once all the (minimum) distances have been calculated, the route from the beginning to the end can be calculated.
Most folks would use a recursive, depth-first search to solve this problem. Some implementations (not the one below!) have the slight problem of using potentially too much memory when the target matrix has lots of potential solutions. If memory is an issue, a breadth-first search would probably be a better solution (it will create a sort of 'wave' emanating from the origin).
Depth-first searches are pretty easy to implement recursively. Basically, one starts at the 'origin' (wherever that is) and invokes a routine to 'walk' to all legal squares. Each walk requires incrementing the distance and re-invoking 'walk' to new squares'. Of course, if a shorter route already exists, there's no reason to 'walk' to a square.
The solution below exploits the notion that only *one* solution is required, not an optimum solution (which often requires back-threading through a path to find the intermediate squares of the answer).
This compact answer is the C solution of USACO alumnus Hooyoung Chung. Comments were added by Coach Rob:
#include <stdio.h> char X[113][78]; /* the maze */ int pr[8702], pc[8702], K, R, C; /* solution r,c list */ int dfs (int r, int c, int k) { /* row, column, distance */ if (r == R - 1 && c == C - 1) { /* done? */ K = k; /* record length of solution */ return 1; /* unwind all the way home */ } /* ordering of the conditions is important */ /* since must not check X[r][c] until r and c are validated */ if (k >= 8702 || /* too far */ r < 0 || r >= R || /* illegal row */ c < 0 || c >= C || /* illegal column */ X[r][c] != '.') /* illegal destination square */ return 0; pr[k] = r; /* record current path */ pc[k] = c; /* frequent overwrites until ans found */ X[r][c] = '@'; /* tag square as 'used' */ return (dfs(r + 1, c, k + 1) || /* soln via r+1,c */ dfs(r - 1, c, k + 1) || /* soln via r-1,c */ dfs(r, c + 1, k + 1) || /* soln via r,c+1 */ dfs(r, c - 1, k + 1)); /* soln via r,c-1 */ } int main (void) { int i; freopen("skate.in", "r", stdin); /* input file */ freopen("skate.out", "w", stdout); /* outputput file */ scanf("%d%d", &R, &C); for (i = 0; i < R; i++) scanf("%s", X + i); dfs(0, 0, 0); for (i = 0; i < K; i++) /* R,C are off by 1 from C indexing */ printf("%d %d\n", pr[i]+1, pc[i]+1); printf("%d %d\n", R, C); /* weren't saved by dfs() */ return 0; }