## Interview Question

## Interview Answer

6 Answers

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(); } }

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); } */

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.

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

A* Algorithm Wikipedia has a nice animated image to describe it

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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; }