Java Maze solver program

Copy , paste, run... The ones are the walls in the below matrix and zeroes are open ways in the labyrinth. We are trying to find shortest path to the given destination : which is (x,y)-> (19,8) here in the example Just modify the maze by playing with the Ones and Zeroes and run it in your local

	package com.company.samples.way8;
	public class JavaMazeSolver {
	public static void main (String[] args) {
	// A sample maze to solve...
	// We will try to reach to cell [6][8] = val-> (-1)
	int exitRow = 19;
	int exitColumn = 8;
	// One(s)=1 are the blocked cells,
	// Zero(s)=0 are the open cells
	int[][] maze = new int[][]{
	//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },//0
	{ 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//1
	{ 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//2
	{ 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//3
	{ 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//4
	{ 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//5
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//6
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },//7
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//8
	{ 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//9
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//10
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },//11
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//12
	{ 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//13
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//14
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },//15
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//16
	{ 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },//17
	{ 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//18
	{ 1, 0, 1, 0, 1, 1, 1, 1,-1, 1, 1, 1, 1, 1, 1, 1 },//19
	{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },//20
	{ 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 } //21
	};
	// This is someting like linkedList...
	// We need a two dimensional array, same sized with the given maze
	LinkedMatrixCell[][] linkedMatrixMatrixCell = new LinkedMatrixCell[maze.length][maze[0].length] ;
	// Let each cell know the map
	LinkedMatrixCell.setLinkedMatrixCellMaze (linkedMatrixMatrixCell);
	// This will build up our whole/complete map, see this constructor
	// You can print the maze after calling this if you want
	new LinkedMatrixCell (0,0, maze, 0);
	// now it is time to call out recursive function starting from the destination
	findMinPathToTarget ( maze, exitRow, exitColumn, 0);
	// And lets see some isThisTheShortestPath huh ??
	displayTheNavigatableMap ( LinkedMatrixCell.getLinkedMatrixCellMaze ());
	}
	private static void displayTheNavigatableMap (LinkedMatrixCell[][] linkedMatrixCellMaze) {
	for (int i = 0; i < linkedMatrixCellMaze.length; i++) {
	for (int j = 0; j < linkedMatrixCellMaze[0].length; j++) {
	if(linkedMatrixCellMaze[i][j] != null){
	System.out.print ("(" + String.format ("%03d",Integer.parseInt (linkedMatrixCellMaze[i][j].toString ())) + ") ");
	}else{
	System.out.print ("(**) ");
	}
	}
	System.out.println ();
	}
	System.out.println ("linkedMatrixCellMaze = " + linkedMatrixCellMaze);
	}
	public static int findMinPathToTarget (int[][] maze, int exitRow, int exitCol, int distance) {
	LinkedMatrixCell[][] linkedMatrixCellMaze = LinkedMatrixCell.getLinkedMatrixCellMaze ();
	LinkedMatrixCell currentCell = linkedMatrixCellMaze[exitRow][exitCol];
	DistanceResult distanceResult = currentCell.setDistance2Start (distance);
	int oneMoreStep = distance + 1;
	DistanceResult distanceSetResult = null;
	// try to go left
	if (currentCell.left != null) {
	distanceSetResult = currentCell.left.setDistance2Start (oneMoreStep);
	if (exitCol -1 >= 0 && distanceSetResult.isThisTheShortestPath == true)
	findMinPathToTarget (maze, exitRow, exitCol -1, distanceSetResult.getDistance ());
	}
	// try to go right
	if (currentCell.right != null) {
	distanceSetResult = currentCell.right.setDistance2Start (oneMoreStep);
	if(exitCol + 1 <= linkedMatrixCellMaze[0].length && distanceSetResult.isThisTheShortestPath == true)
	findMinPathToTarget (maze, exitRow, exitCol + 1, distanceSetResult.getDistance ());
	}
	// try to go down
	if (currentCell.down != null) {
	distanceSetResult = currentCell.down.setDistance2Start (oneMoreStep);
	if(exitRow <= linkedMatrixCellMaze.length && distanceSetResult.isThisTheShortestPath == true)
	findMinPathToTarget (maze, exitRow + 1, exitCol, distanceSetResult.getDistance ());
	}
	// try to go up
	if (currentCell.up != null) {
	distanceSetResult = currentCell.up.setDistance2Start (oneMoreStep);
	if(exitRow >= 0 && distanceSetResult.isThisTheShortestPath == true)
	findMinPathToTarget (maze, exitRow -1, exitCol, distanceSetResult.getDistance ());
	}
	return distance;
	}
	static class LinkedMatrixCell {
	// let each cell has the map information
	static LinkedMatrixCell[][] linkedMatrixCellMaze;
	// cell coordinates : value can be 0 (open road), 1 (blocked road) , -1 (destination)
	int xPosition , yPosition , value;
	// I will drive my code to find always smaller distances if possible
	int distance2Start = Integer.MAX_VALUE -1;
	// let each cell get linked to its neighbours
	LinkedMatrixCell up, down,left, right = null;
	public LinkedMatrixCell (int xPosition, int yPosition, int[][] maze, int distance2Start) {
	linkedMatrixCellMaze[xPosition][yPosition] = this;
	this.xPosition = xPosition;
	this.yPosition = yPosition;
	this.value = maze[this.xPosition][this.yPosition];
	// I would refactor the below statements but i guess these are more readable & understandable
	if (this.yPosition > 0 && maze[xPosition][yPosition - 1] != 1) {
	if (linkedMatrixCellMaze[xPosition][yPosition - 1] == null) this.left = new LinkedMatrixCell (xPosition, yPosition - 1, maze, distance2Start + 1);
	else this.left = linkedMatrixCellMaze[xPosition][yPosition - 1];
	}
	if (this.yPosition < maze[0].length - 1 && maze[xPosition][yPosition + 1] != 1) {
	if (linkedMatrixCellMaze[xPosition][yPosition + 1] == null) this.right = new LinkedMatrixCell (xPosition, yPosition + 1, maze,distance2Start + 1);
	else this.right = linkedMatrixCellMaze[xPosition][yPosition + 1];
	}
	if (this.xPosition > 0 && maze[xPosition - 1][yPosition] != 1) {
	if (linkedMatrixCellMaze[xPosition - 1][yPosition] == null) this.up = new LinkedMatrixCell (xPosition - 1, yPosition, maze,distance2Start + 1);
	else this.up = linkedMatrixCellMaze[xPosition - 1][yPosition];
	}
	if (this.xPosition < maze.length - 1 && maze[xPosition + 1][yPosition] != 1) {
	if (linkedMatrixCellMaze[xPosition + 1][yPosition] == null) this.down = new LinkedMatrixCell (xPosition + 1, yPosition, maze,distance2Start + 1);
	else this.down = linkedMatrixCellMaze[xPosition + 1][yPosition];
	}
	}
	public static void setLinkedMatrixCellMaze (LinkedMatrixCell[][] linkedMatrixCellMaze) {
	LinkedMatrixCell.linkedMatrixCellMaze = linkedMatrixCellMaze;
	}
	public static LinkedMatrixCell[][] getLinkedMatrixCellMaze () {
	return linkedMatrixCellMaze;
	}
	public int getDistance2Start () {
	return distance2Start;
	}
	public DistanceResult setDistance2Start (int distance2Start) {
	DistanceResult result = new DistanceResult (distance2Start, true);
	DistanceResult result1 = checkOtherSide (distance2Start, this.up);
	if(result1.getDistance () < result.getDistance ()){ result = result1;}
	DistanceResult result2 = checkOtherSide (distance2Start, this.down);
	if(result2.getDistance () < result.getDistance ()){ result = result2;}
	DistanceResult result3 = checkOtherSide (distance2Start, this.left);
	if(result3.getDistance () < result.getDistance ()){ result = result3;}
	DistanceResult result4 = checkOtherSide (distance2Start, this.right);
	if(result4.getDistance () < result.getDistance ()){ result = result4;}
	return result;
	}
	private DistanceResult checkOtherSide (int distance2Start, LinkedMatrixCell sideCell) {
	DistanceResult result;
	if (sideCell != null && sideCell.getDistance2Start () + 1 < distance2Start) {
	this.distance2Start = sideCell.getDistance2Start () + 1;
	result = new DistanceResult (distance2Start, false);
	} else {
	if (this.distance2Start >= distance2Start) {
	this.distance2Start = distance2Start;
	result = new DistanceResult (distance2Start, true);
	} else {
	result = new DistanceResult (this.distance2Start, false);
	}
	}
	return result;
	}
	@Override
	public String toString () {
	return ""+distance2Start ;
	}
	}
	static final class DistanceResult{
	int distance;
	boolean isThisTheShortestPath;
	public DistanceResult (int distance, boolean isThisTheShortestPath) {
	this.distance = distance;
	this.isThisTheShortestPath = isThisTheShortestPath;
	}
	public int getDistance () {
	return distance;
	}
	@Override
	public String toString () {
	return "DistanceResult{" +
	"distance=" + distance +
	'}';
	}
	}
	}

view raw JavaMazeSolver hosted with ❤ by GitHub