## 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 Question, Sign In with Facebook 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;

}