Q: In Java and using recursion and a 2d array. You need to make a maze solver. T
ID: 3690330 • Letter: Q
Question
Q:
In Java and using recursion and a 2d array.
You need to make a maze solver. The program will take in from a file 2 things. The size of the square maze, and the maze itself. The maze will consists of numbers between 0 and 3, where 0 is the starting point of the maze, 1 is an open path, 3 is a wall and blocked , and 2 is the end. The maze will be no larger than 40x40. For example a 6x6 maze could be represented by the following file, there will be no spaces seperating the elements of the maze:
The program must then solve the maze. It will then output the correct path through the maze marked by 0’s to the command line. For example for the maze above could output the following.
000003
333301
110003
330333
330000
333330
You can assume that the input contains the exact amount of numbers needed and that it is a solvable maze, following the rules outlined above.
Explanation / Answer
import java.util.Arrays;
import java.util.Objects;
enum Direction {
UP(-1, 0),
DOWN(1, 0),
LEFT(0, -1),
RIGHT(0, 1);
//config
private final int rowSteps;
private final int colSteps;
private Direction(int rowSteps, int colSteps) {
this.rowSteps = rowSteps;
this.colSteps = colSteps;
}
public int getNewRowIdx(int currentRowIdx) {
return (currentRowIdx + getRowSteps());
}
public int getNewColIdx(int currentColIdx) {
return (currentColIdx + getColSteps());
}
public int getRowSteps() {
return rowSteps;
}
public int getColSteps() {
return colSteps;
}
};
class MazePosition {
//config
private static int[][] MAZE_GRID;
private final int rowIdx;
private final int colIdx;
//internal
private final int rowIdxMinus1;
private final int colIdxMinus1;
public MazePosition(int[][] MAZE_GRID) {
if(this.MAZE_GRID != null) {
throw new IllegalStateException("Maze double-array already set. Use x/y constructor.");
}
MazePosition.MAZE_GRID = MAZE_GRID;
//TODO: Crash if null or empty, or sub-arrays null or empty, or unequal lengths, or contain anything but 0 or -1.
rowIdx = -1;
colIdx = -1;
rowIdxMinus1 = -1;
colIdxMinus1 = -1;
}
public MazePosition(int rowIdx, int colIdx) {
if(MazePosition.MAZE_GRID == null) {
throw new IllegalStateException("Must set maze double-array with: new MazePosition(int[][]).");
}
if(rowIdx < 0 || rowIdx >= MazePosition.getRowCount()) {
throw new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid.");
}
if(colIdx < 0 || colIdx >= MazePosition.getColumnCount()) {
throw new IllegalArgumentException("colIdx (" + colIdx + ") is invalid.");
}
this.rowIdx = rowIdx;
this.colIdx = colIdx;
rowIdxMinus1 = (rowIdx - 1);
colIdxMinus1 = (colIdx - 1);
}
public boolean isPath() {
return (getValue() == 0); //1???
}
public int getValue() {
return MazePosition.MAZE_GRID[getRowIdx()][getColumnIdx()];
}
public int getRowIdx() {
return rowIdx;
}
public int getColumnIdx() {
return colIdx;
}
public MazePosition getNeighbor(Direction dir) {
Objects.requireNonNull(dir, "dir");
return (new MazePosition(
dir.getNewRowIdx(getRowIdx()),
dir.getNewColIdx(getColumnIdx())));
}
public MazePosition getNeighborNullIfEdge(Direction dir) {
if(isEdgeForDirection(dir)) {
return null;
}
return getNeighbor(dir);
}
public int getNeighborValueNeg1IfEdge(Direction dir) {
MazePosition pos = getNeighborNullIfEdge(dir);
return ((pos == null) ? -1 : pos.getValue());
}
public static final int getRowCount() {
return MAZE_GRID.length;
}
public static final int getColumnCount() {
return MAZE_GRID[0].length;
}
public boolean isEdgeForDirection(Direction dir) {
Objects.requireNonNull(dir);
switch(dir) {
case UP: return isTopEdge();
case DOWN: return isBottomEdge();
case LEFT: return isLeftEdge();
case RIGHT: return isRightEdge();
}
throw new IllegalStateException(toString() + ", dir=" + dir);
}
public boolean isLeftEdge() {
return (getColumnIdx() == 0);
}
public boolean isTopEdge() {
return (getRowIdx() == 0);
}
public boolean isBottomEdge() {
return (getRowIdx() == rowIdxMinus1);
}
public boolean isRightEdge() {
return (getColumnIdx() == colIdxMinus1);
}
public String toString() {
return "[" + getRowIdx() + "," + getColumnIdx() + "]=" + getValue();
}
public String getNineByNine() {
int[][] nineByNine = new int[3][3];
//Middle row
nineByNine[1][1] = getValue();
nineByNine[1][0] = getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[1][2] = getNeighborValueNeg1IfEdge(Direction.RIGHT);
//Top
MazePosition posUp = getNeighborNullIfEdge(Direction.UP);
if(posUp != null) {
nineByNine[0][0] = posUp.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[0][1] = posUp.getValue();
nineByNine[0][2] = posUp.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
//Bottom
MazePosition posDown = getNeighborNullIfEdge(Direction.DOWN);
if(posDown != null) {
nineByNine[2][0] = posDown.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[2][1] = posDown.getValue();
nineByNine[2][2] = posDown.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
String sLS = System.getProperty("line.separator", " ");
return "Middle position in 9x9 grid is *this*: " + toString() + sLS +
Arrays.toString(nineByNine[0]) + sLS +
Arrays.toString(nineByNine[1]) + sLS +
Arrays.toString(nineByNine[2]);
}
}
public class MazePosDemo {
private static final int[][] MAZE_GRID = new int[][] {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
{1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
{1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
{1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
{1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
{1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
{1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
{1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);
public static final void main(String[] ignored) {
MazePosition pos = new MazePosition(0, 0);
System.out.println("start: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.LEFT);
System.out.println("left: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
System.out.println(pos.getNineByNine());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.