Maze, assumption - single point of entry and a single point of exit. Also directions to travel in maze are North South East West. Request for optimization and code cleanup.
final class Coordinate {
private final int x;
private final int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null)
return false;
if (getClass() != o.getClass())
return false;
// now to the check.
final Coordinate coordinate = (Coordinate) o;
return coordinate.x == x && coordinate.y == y;
}
public int hashCode() {
return x + y;
}
}
public class Maze {
private final int[][] maze;
public Maze(int[][] maze) {
if (maze == null) {
throw new NullPointerException("The input maze cannot be null");
}
if (maze.length == 0) {
throw new IllegalArgumentException("The size of maze should be greater than 0");
}
this.maze = maze;
}
public Set<Coordinate> solve() {
Set<Coordinate> setCoordinate = new LinkedHashSet<Coordinate>();
for (int j = 0; j < maze[0].length; j++) {
if (maze[0][j] == 1) {
getMazePath(0, j, setCoordinate);
return setCoordinate;
}
if (maze[maze.length - 1][j] == 1) {
getMazePath(maze.length - 1, j, setCoordinate);
return setCoordinate;
}
}
// note - we dont want to double count tile.
for (int i = 1; i < maze.length - 1; i++) {
if (maze[i][0] == 1) {
getMazePath(i, 0, setCoordinate);
return setCoordinate;
}
if (maze[i][maze[0].length - 1] == 1) {
getMazePath(i, maze[0].length - 1, setCoordinate);
return setCoordinate;
}
}
throw new IllegalArgumentException("The input maze does not have an entry point");
}
private boolean getMazePath(int row, int col, Set<Coordinate> set) {
assert set != null;
if (set.contains(new Coordinate(row, col))) return false;
if ((((row == 0) || (row == maze.length - 1)) || ((col == maze[0].length - 1) || col == 0)) && !set.isEmpty() /* discard the entry tile */) {
set.add(new Coordinate(row, col));
return true;
}
set.add(new Coordinate(row, col));
boolean getMaze = false;
/**
* travel in all 4 language
*/
if (((col - 1) >= 0) && (maze[row][col - 1] == 1) && !getMaze) {
getMaze = getMazePath(row, col - 1, set);
}
if (((row - 1) >= 0) && (maze[row - 1][col] == 1) && !getMaze) {
getMaze = getMazePath(row - 1, col, set);
}
if (((col + 1) < maze[0].length) && (maze[row][col + 1] == 1) && !getMaze) {
getMaze = getMazePath(row, col + 1, set);
}
if (((row + 1) < maze.length) && (maze[row + 1][col] == 1) && !getMaze) {
getMaze = getMazePath(row + 1, col, set);
}
if (!getMaze) {
set.remove(new Coordinate(row, col));
}
return getMaze;
}
public static void main(String[] args) {
int[][] m1 = { { 0, 1, 0 },
{ 1, 1, 0 },
{ 0, 0, 0 } };
for (Coordinate coord : new Maze(m1).solve()) {
System.out.println(coord.getX() + " : " + coord.getY());
}
System.out.println("-------------------------------------");
int[][] m2 = { { 0, 0, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 0 },
{ 1, 1, 1, 0 },
{ 0, 0, 0, 0 } };
for (Coordinate coord : new Maze(m2).solve()) {
System.out.println(coord.getX() + " : " + coord.getY());
}
}
}
hashCode()
return the same hash code for (1,2) and (2,1)? \$\endgroup\$ – Mathieu Guindon♦ Oct 26 '13 at 23:03