Searches for a destination cell from a source cell in a 3D matrix via shortest path

HermanWorm.java

/* 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
 *          [email protected]
 * @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

  //-------------------------------------------------------------------------------------------------
}