CareerCup

Interesting problem. Very similar to the TopCoder problem found here:
http :// community.topcoder.com/stat?c=problem_statement&pm=1889

Assume (0, 0) is top-left corner, and (m, n) is bottom-right.
Then, the basic idea is:
1. Let K(i, j) be the ways in which you can get to (m, n) from (i, j).
2. In a highly compressed formula, the recurrence relation is:

K(i, j)  = {(i-1, j) reachable}?K(i-1, j):0 + {(i, j+1) reachable}?K(i, j+1):0  

	where i = m-1, m-2, ..., 2, 1 & j = n-1, n-2, ..., 2, 1

For getting base conditions, we observe:
3. K(m-1, n-1) = 2 (Since you can go {East + South} or {South + East} to get to (m,n))
4. K(m-1, n-2) = 1 + K(m-1, n-1)
5. K(m-1, n-3) = 1 + K(m-1, n-2) and so on...
6. Similarly, for the vertical last column, K(m-2, n-1) = 1 + K(m-1, n-1)
7. K(m-3, n-1) = 1 + K(m-2, n-1) and so on.

Note*: There may be some points in the last column/row that are unreachable. This calls for a slight modification from steps (3) through (7), that are really similar to the formula in step (2). This is left as an exercise to the reader :)

Note**: The above algorithm also has within it, a neatly embedded heuristic: "I can only move in the downward or right directions"! This I think, is justified, since you constantly want to be moving in the direction of your target (m, n). This is also something you can talk to the interviewer about. If the interviewer wants to incorporate another direction into allowable directions (say, left), then we simply change the recursion formula to reflect so.

Time complexity: O(mn)
Space complexity: O(mn)

I created the solution below for this problem. I don't think it is optimal, I think it could be improved but it works.

The results it throws seem to be backwards in terms of (X, Y), but I think that is because the way I declared the char array that represents the maze.

The maze I created is shown below. The "#" means obstacle, "." means free path, "+" is used by the algorithm to mark cells each recursion has visited and G marks the goal.

Maze:
.##....
.##.##.
.....#.
#.##.#.
#.#..#.
#.#.###
#......

static void Main(string[] args)
        {            
            char[,] maze = new char[7, 7] {{'.', '#', '#', '.','.','.','.',},
                                           {'.', '#', '#', '.','#','#','.',},
                                           {'.', '.', '.', '.','.','#','.',},
                                           {'#', '.', '#', '#','.','#','.',},
                                           {'#', '.', '#', '.','.','#','.',},
                                           {'#', '.', '#', '.','#','#','#',},
                                           {'#', '.', '.', '.','.','.','G',},
                                          };

            string[] solutions = FindMazeSolutions(ref maze, new Position(0,0));
        }

    public class Position
    {
        public int X { get; set; }
        public int Y { get; set; }

        public Position(int x, int y)
        {
            this.X = x;
            this.Y = y;
        }
    }

        //"(0,0) (0,1) (0,2) (1,2)... (6,6)"
        //"(0,0) (1,0) (2,0) (2,1)... (6,6)"
        static string[] FindMazeSolutions(ref char[,] maze, Position startPosition)
        {
            List<string> solutions = new List<string>();
            string[] resultsFromNorth;
            string[] resultsFromEast;
            string[] resultsFromSouth;
            string[] resultsFromWest;

            if (startPosition.X < 0 || startPosition.X >= maze.GetLength(0) || startPosition.Y < 0 || startPosition.Y >= maze.GetLength(1))
                return null;

            if (maze[startPosition.X, startPosition.Y] == '#' || maze[startPosition.X, startPosition.Y] == '+')
                return null;

            if (maze[startPosition.X, startPosition.Y] == 'G')
                return new string[] { String.Format("({0},{1})", startPosition.X.ToString(), startPosition.Y.ToString()) };

            maze[startPosition.X, startPosition.Y] = '+';

            resultsFromNorth = FindMazeSolutions(ref maze, new Position(startPosition.X, startPosition.Y + 1));
            if (resultsFromNorth != null)
            {
                foreach (string solution in resultsFromNorth)
                {
                    solutions.Add(String.Format("({0},{1}) {2}", startPosition.X.ToString(), startPosition.Y.ToString(), solution));
                }
            }

            resultsFromEast = FindMazeSolutions(ref maze, new Position(startPosition.X + 1, startPosition.Y));
            if (resultsFromEast != null)
            {
                foreach (string solution in resultsFromEast)
                {
                    solutions.Add(String.Format("({0},{1}) {2}", startPosition.X.ToString(), startPosition.Y.ToString(), solution));
                }
            }

            resultsFromSouth = FindMazeSolutions(ref maze, new Position(startPosition.X, startPosition.Y - 1));
            if (resultsFromSouth != null)
            {
                foreach (string solution in resultsFromSouth)
                {
                    solutions.Add(String.Format("({0},{1}) {2}", startPosition.X.ToString(), startPosition.Y.ToString(), solution));
                }
            }

            resultsFromWest = FindMazeSolutions(ref maze, new Position(startPosition.X - 1, startPosition.Y));
            if (resultsFromWest != null)
            {
                foreach (string solution in resultsFromWest)
                {
                    solutions.Add(String.Format("({0},{1}) {2}", startPosition.X.ToString(), startPosition.Y.ToString(), solution));
                }
            }

            maze[startPosition.X, startPosition.Y] = '.';

            return solutions.ToArray();
        }