Interview Question

Software Development Engineer Interview Seattle, WA

"Solve a maze", you have a 2D matrix with 1's as blocked

  s path. Find a path from one corner to another, backtracking should be allowed.
Answer

Interview Answer

6 Answers

0

Might be a little sloppy, but it works.

    public static int solveMaze(int[][] maze, int i, int j, int oldi, int oldj) {
        int solved = 0;
        if((i+1) == maze.length && (j+1) == maze[i].length) {
            return 1;
        }

        if((j-1) >= 0 && (j-1) != oldj && maze[i][j-1] == 0) {
            solved = solveMaze(maze, i, j-1, i, j);
        } if(solved != 1 && (i-1) >= 0 && (i-1) != oldi && maze[i-1][j] == 0) {
            solved = solveMaze(maze, i-1, j, i, j);
        } if(solved != 1 && (j+1) < maze[i].length && (j+1) != oldj && maze[i][j+1] == 0) {
            solved = solveMaze(maze, i, j+1, i, j);
        } if(solved != 1 && (i+1) < maze.length && (i+1) != oldi && maze[i+1][j] == 0) {
            solved = solveMaze(maze, i+1, j, i, j);
        }
        return solved;
    }

Curtis on Jan 27, 2012
0

Here is the maze.

  1 1 1 1 1 1 1 1 1 1 1 1
  1 0 0 0 1 0 0 0 0 0 0 1
  0 0 1 0 1 0 1 1 1 1 0 1
  1 1 1 0 1 0 0 0 0 1 0 1
  1 0 0 0 0 1 1 1 0 1 0 1
  1 1 1 1 0 1 F 1 0 1 0 1
  1 0 0 1 0 1 0 1 0 1 0 1
  1 1 0 1 0 1 0 1 0 1 0 1
  1 0 0 0 0 0 0 0 0 1 0 1
  1 1 1 1 1 1 0 1 1 1 0 1
  1 0 0 0 0 0 0 1 0 0 0 1
  1 1 1 1 1 1 1 1 1 1 1 1

public class MazePath {

    char[][] maze = new char[12][12];

     Queue<Node> queue = new LinkedList<Node>();
    // Define the starting point and endpoint in a node.
    Node startingPoint = new Node(1,1);
    Node endPoint = new Node(10,10);

    Map<Node,Node> hm = new HashMap<Node,Node>();

    public void createArray() throws IOException{
        // read maze from a file and create an array
         FileInputStream in = new FileInputStream("c:/Personal/Maze.txt");
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine;
            for(int j = 0; j<maze.length; j++)
            {
                maze[j] = br.readLine().replaceAll(" ", "").toCharArray();
            }

            System.out.println(maze[2][0]);
    }

        public void findPathBreadthFirt(){
            queue.add(startingPoint);

            hm.put(startingPoint, startingPoint);

            while(!queue.isEmpty()){
                Node n = queue.poll();
                if(n.equals(endPoint)){
                    printPathUsingParent(n);
                    break;
                }
                addAdjacentVertices(n);
            }

        }

        public void printPathUsingParent(Node destination){

            Node current = destination;
            while(current.parentNode!=null){
                System.out.println(current.toString());
                current = current.parentNode;
            }

            System.out.println(current.toString());
        }

        public void addAdjacentVertices(Node v){
                Node v1 =v;
                int row = v1.row;
                int column=v1.column;
                boolean added =false;

                //check if any point exist in the top side and add it in the Queue
                if(v1.row!=0 ){
                     if(convertCharToInt(maze[row-1][column])==0 ){
                         Node top = new Node(row-1,column);

                         if(!hm.containsKey(top)){
                             addIntoMapAndStack(top,v);
                             added=true;

                         }
                     }
                }

                // check point in the bottom and add it int he queue
                if(v1.row!=maze.length){
                     if(convertCharToInt(maze[row+1][column])==0){
                         Node bottom = new Node(row+1,column);
                         if(!hm.containsKey(bottom)){
                              addIntoMapAndStack(bottom,v);
                             added=true;
                         }
                     }
                }

                // check point in the right and add

                if(v1.column!=maze[1].length){
                       if(convertCharToInt(maze[row][column+1])==0){
                         Node right = new Node(row,column+1);
                         if(!hm.containsKey(right)){
                              addIntoMapAndStack(right,v); added=true;
                         }
                     }
                }

                // check point in the left and add.
                if(v1.column!=0){
                     if(convertCharToInt(maze[row][column-1])==0){
                        Node left = new Node(row,column-1);
                         if(!hm.containsKey(left)){

                             addIntoMapAndStack(left,v);
                             added=true;
                         }
                     }
                }

        }

        public int convertCharToInt(char c){
            return Character.getNumericValue(c);
        }

        public void addIntoMapAndStack(Node v,Node parentNode){
            v.setParentNode(parentNode);
            stack.add(v);
            queue.add(v);
            hm.put(v, v);

        }

             public static void main(String [] args) throws IOException
        {
            MazePath mp = new MazePath();
            mp.createArray();
        // mp.findPathDepthFirt();
             mp.findPathBreadthFirt();
        }
        }

Anand on Jan 31, 2012
0

My previous answer was an implementation and here brief description on the implementation.

 * 1) Read a maze from file and convert into a int[][] array.
 * 2) Declare starting point and end point
 * 3) declare Queue and add startingPoint in that queue.
 * 4) Deque the node from Queue and find all the possible path add it in the queue again.
 * 5) Each Node contains a reference to their parent Node. Starting point doesn't contains any reference to the parent node.
 * 6) While dequeing a node, if it matches with endpoint then traverse back to the starting point and that's the path of the maze.
 * 7) To avoid duplicate traversing, create a visited=true flag or use HashMap.
 *
 * queue.add(startingPoint);
 * hm.put(startingPoint, startingPoint);
              while(!queue.isEmpty()){
                Node n = queue.poll();
                if(n.equals(endPoint)){
                    printPathUsingParent(n);
                    break;
                }
                addAdjacentVertices(n);
            }
 */

Anonymous on Jan 31, 2012
0

Here is a concept that may works, starting from the beginning point, each step could lead to possibly three path, we can draw a tree which each node has three children (max), then find the longest path would do it, each dead end will determine if the current node has any child or not.

needajob on Feb 1, 2012
1

enter the maze into a graph data structure where adjacent 0's are connected to each other with an edge. Label the starting and ending points, and do a DFS from the starting location.

This would be an internal solution, as there would be no visual representation of it, but you could easily enough attach coordinates to each node to allow for a visual solution

PC on Feb 14, 2012
0

A* Algorithm

Wikipedia has a nice animated image to describe it

Anonymous on Jan 19, 2013

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up