Shortest Distance in X x Y x Z 3D Matrix - Efficient BFS Method

$\mathtt{REFERENCE}$ @ HackerRank

$\mathtt{RELATED\ PROBLEM}$ The problem is related to path searching in 2D matrix. Only Difference is here we are dealing with 3D matrix. Searching in 2D matrix problem can be found HERE

Task Description

Herman the worm is in his terrarium and needs help getting to a grape to eat. His terrarium is $x \times y \times z$ large and is blocked by obstacles throughout the environment.

Please write an algorithm that outputs an optimal path Herman must take to get to the grape.

$H = Herman's\ starting\ point$
$O = Open$
$X = Obstacle\ (closed)\ Herman\ can't\ travel\ this\ way.$
$G = Grape$

Input Format

The first line of input will be $x,\ y,\ z$ in the format: $x\ y\ z$
Where, $x$ is the length of the X-Axis, $y$ is the length of the Y-Axis and $z$ is the length of the Z-Axis.

This will be followed by a layout of $x, y$ map for each of $z$ layer separated by a $blank\ line$.

Constraints

$0 <= X, Y, Z <= 40$

Output Format

Output will be sequence of Motion required to reach the destionation cell G from the source Cell H in separate lines.

Sample Inputs and Outputs

Sample Input 0

2 3 2

HX
OX
OX

XG
XO
OO

Sample Output 0

Y+
Y+
Z+
X+
Y-
Y-

Sample Input 1

3 3 2

HXG
OXX
OXX

XXO
XXO
OOO

Sample Output 1

Y+
Y+
Z+
X+
X+
Y-
Y-
Z-

Sample Input 2

4 4 4

GOOO
OOXO
OOOO
OOOO

OXXX
XXHX
XXXX
XXXX

OXXX
XXOX
XXXX
XXXX

OXXO
OOOO
OOOO
OOOO

Sample Output 2

Z+
Z+
X-
X-
Y-
Z-
Z-
Z-

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution: BFS Method - Efficient Method

Similar to the path searching Problem in 2D Matrix, this problem can also be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be $\cal{O(xyz)}$.

Implementation

	/* File: HermanWorm.java
	* Created: 5/24/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* Finds the shortest distance from source to destination in
	* 3D array
	*
	* @author Sabbir Manandhar
	* manandhar.sabbir@gmail.com
	* @version 1.0
	*/
	public class HermanWorm {
	private static int X, Y, Z;
	/**
	* Driver Method
	* Reads Input from console as explained in the post
	*
	* @param args
	* @throws Exception
	*/
	public static void main(String[] args) throws Exception {
	Scanner sc = new Scanner(System.in);
	X = sc.nextInt();
	Y = sc.nextInt();
	Z = sc.nextInt();
	//System.out.println(X + " " + Y + " " + Z);
	sc.nextLine();
	sc.nextLine();
	Cell[][][] maze = new Cell[X][Y][Z];
	int sx = -1, sy = -1, sz = -1;
	for (int z = 0; z < Z; z++) {
	for (int y = 0; y < Y; y++) {
	String line = sc.nextLine();
	//System.out.println(line);
	if (line.length() != X) throw new Exception("Error reading input");
	for (int x = 0; x < X; x++) {
	char c = line.charAt(x);
	if(c == 'H') {
	sx = x;
	sy = y;
	sz = z;
	}
	maze[x][y][z] = new Cell(c, new int[]{x, y, z});
	}
	}
	if (sc.hasNextLine()) sc.nextLine();
	}
	//System.out.println(sx + " " + sy + " " + sz);
	solve(maze, sx, sy, sz);
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Searches for the Destination cell in a BFS fashion
	*
	* @param matrix 3D matrix where we need to find the destination cell from source
	* @param x source x location
	* @param y source y location
	* @param z source z location
	* @throws Exception
	*/
	public static void solve(Cell[][][] matrix, int x, int y, int z) throws Exception {
	// delta values to find neighboring cells of current cell
	int[][] delta = new int[][]{{-1, 0, 0}, // negative X
	{1, 0, 0}, // positive X
	{0, -1, 0}, // negative Y
	{0, 1, 0}, // positive Y
	{0, 0, -1}, // negative Z
	{0, 0, 1}}; // positive Z
	Queue<Cell> queue = new LinkedList<Cell>();
	Cell source = matrix[x][y][z];
	queue.offer(source);
	while (!queue.isEmpty()) {
	Cell parent = queue.poll();
	for (int i = 0; i < delta.length; i++) {
	// location of neighbor cell
	int nx = parent.getLocation()[0] + delta[i][0];
	int ny = parent.getLocation()[1] + delta[i][1];
	int nz = parent.getLocation()[2] + delta[i][2];
	if (isValidLocation(nx, ny, nz)) {
	Cell neighbor = matrix[nx][ny][nz];
	if (!neighbor.isVisited() && !neighbor.isObstacle()) {
	neighbor.setParent(parent);
	neighbor.setVisited();
	//System.out.println(neighbor);
	neighbor.setMotion(getMotion(parent, neighbor));
	if (neighbor.isDestination()) {
	printResult(neighbor);
	return;
	} else {
	queue.offer(neighbor);
	}
	}
	}
	}
	}
	} // solve
	//---------------------------------------------------------------------------------------------------
	/**
	* Motion required to move from Source cell to Destination Cell
	* @param source Source Cell
	* @param destination Destination Cell
	* @return X+ if the motion needed is positive unit distance in X direction
	* X- if the motion needed is negative unit distance in X direction
	* Y+ if the motion needed is positive unit distance in Y direction
	* Y- if the motion needed is negative unit distance in Y direction
	* Z+ if the motion needed is positive unit distance in Z direction
	* Z- if the motion needed is negative unit distance in Z direction
	* @throws Exception
	*/
	private static String getMotion(Cell source, Cell destination) throws Exception {
	int dx = destination.getLocation()[0] - source.getLocation()[0];
	int dy = destination.getLocation()[1] - source.getLocation()[1];
	int dz = destination.getLocation()[2] - source.getLocation()[2];
	if (dx == 1 && dy == 0 && dz == 0) return "X+";
	if (dx == -1 && dy == 0 && dz == 0) return "X-";
	if (dy == 1 && dx == 0 && dz == 0) return "Y+";
	if (dy == -1 && dx == 0 && dz == 0) return "Y-";
	if (dz == 1 && dy == 0 && dx == 0) return "Z+";
	if (dz == -1 && dy == 0 && dx == 0) return "Z-";
	throw new Exception("getMotion: Something is wrong");
	} // getMotion
	//--------------------------------------------------------------------------------------------------
	/**
	* Print the result once the destination cell is found
	* This is Recursive implementation
	* @param dest Destination Cell
	*/
	private static void printResult(Cell dest) {
	if (dest.isSource()) {
	return;
	}
	printResult(dest.getParent());
	System.out.println(dest.getMotion());
	} // printResult
	//--------------------------------------------------------------------------------------------------
	/**
	* Determine is the location represented by inputs is a valid location in the
	* given input matrix
	* @param x x location
	* @param y y location
	* @param z z location
	* @return True if the location is within the matrix else False
	*/
	public static boolean isValidLocation(int x, int y, int z) {
	return !(x < 0 || x >= X || y < 0 || y >= Y || z < 0 || z >= Z);
	} // isValidLocation
	//---------------------------------------------------------------------------------------------------
	} // HermanWorm
	//====================================================================================================
	/**
	* Class representing a Cell in a Matrix
	*/
	class Cell {
	private int[] location;
	private char c;
	private boolean visited;
	private Cell parent;
	private String motion;
	/**
	* Constructor
	* @param c character in the cell
	* @param location [x,y,z] location triplet
	*/
	public Cell(char c, int[] location) {
	this.c = c;
	this.location = location;
	this.visited = false;
	this.parent = null;
	} // Cell
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets the cell as visited
	*/
	public void setVisited() {
	visited = true;
	} // setVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets parent of the cell during the search to a destination via shortest path
	* Parent is the parent of this cell in the path
	* @param parent
	*/
	public void setParent(Cell parent) {
	this.parent = parent;
	} // setParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine whether the cell is visited
	* @return true if the cell is visited, else false
	*/
	public boolean isVisited() {
	return this.visited;
	} // isVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Get parent of this cell in the path, if already set
	* @return the parent cell if it has been set, else it will be null
	*/
	public Cell getParent() {
	return this.parent;
	} // getParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a destination cell
	* @return True if this cell is a destination cell, else false
	*/
	public boolean isDestination() {
	return this.c == 'G';
	} // isDestination
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is an obstacle
	* @return True if this cell is an obstacle, false otherwise
	*/
	public boolean isObstacle() {
	return this.c == 'X';
	} // isObstacle
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a source
	* @return True if this cell is source, false otherwise
	*/
	public boolean isSource() {
	return this.c == 'H';
	} // isSource
	//-------------------------------------------------------------------------------------------------
	/**
	* Get the motion which is required to reach this cell from the parent cell in the shortest path
	* @return the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public String getMotion() {
	return this.motion;
	} // getMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* Sest the motion to reach this cell from the parent cell
	* @param motion the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public void setMotion(String motion) {
	this.motion = motion;
	} // setMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* get the x, y, z location triplet of this cell in the input matrix
	* @return
	*/
	public int[] getLocation() {
	return this.location;
	} // getLocation
	//-------------------------------------------------------------------------------------------------
	/**
	* String representation of this cell
	* Written for debug pupose
	* @return
	*/
	public String toString() {
	return this.c + " " + this.visited + " " + (this.parent != null ? this.parent.c : null);
	} // toString
	//-------------------------------------------------------------------------------------------------
	}

view raw HermanWorm.java hosted with ❤ by GitHub

---

---

---