import java.io.*;
import java.util.*;
import java.util.ArrayList;
public class lab29a
{
public static void main(String args[]) throws IOException
{
System.out.println("\nLab 29a \n");
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter random starting seed ===>> ");
int seed = Integer.parseInt(input.readLine());
Maze maze = new Maze(seed);
maze.displayMaze();
maze.solveMaze();
maze.displayMaze();
maze.mazeSolution();
}
}
class Coord // Coord is a class that stores a single maze location.
{
private int rPos;
private int cPos;
public Coord (int r, int c) { rPos = r; cPos = c; }
public boolean isFree() { return (rPos == 0 && cPos == 0);}
public void setPos(int r, int c) { rPos+= r; cPos+= c; }
public int getrPos() { return rPos; }
public int getcPos() { return cPos; }
}
class Maze
{
private char mat[][]; // 2d character array that stores the maze display
private Coord currentMove; // object that stores current maze position
private MyStack visitStack; // stack that stores location that have been visited
// constructor which generates the random maze, random starting location
// and initializes Maze class values. If the random value equals 0 the maze
// store an 'X' otherwise it store an 'O' in the maze.
public Maze(int seed)
{
Random random = new Random(seed);
int startRow, startCol;
mat = new char[12][12];
for (int r = 0; r < 12; r++)
for (int c = 0; c < 12; c++)
{
if (r == 0 || c == 0 || r == 11 || c == 11)
mat[r][c] = 'X';
else
{
int rndInt = random.nextInt(2);
if (rndInt == 0)
mat[r][c] = 'X';
else
mat[r][c] = 'O';
}
}
mat[0][0] = 'O';
startRow = random.nextInt(12);
startCol = 11;
mat[startRow][startCol] = '.';
visitStack = new MyStack();
currentMove = new Coord(startRow,startCol);
visitStack.push(currentMove);
}
// displays the current maze configuration
void displayMaze() throws IOException
{
System.out.println("\nRANDOM MAZE DISPLAY\n");
for (int r = 0; r < 12; r++)
{
for (int c = 0; c < 12; c++)
System.out.print(mat[r][c] + " ");
System.out.println();
}
System.out.println();
pause();
}
// This method solves the maze with private helper method <getMove>.
// A loop is needed to repeat getting new moves until either a maze solution
// is found or it is determined that there is no way out off the maze.
public void solveMaze() throws IOException
{
System.out.println("\n>>>>> WORKING .... SOLVING MAZE <<<<<\n");
while(getMove())
{
mat[currentMove.getrPos()][currentMove.getcPos()] = '.';
}
}
// Short method to display the result of the maze solution
public void mazeSolution()
{
if (currentMove.isFree())
System.out.println("\nTHE MAZE HAS A SOLUTION.\n");
else
System.out.println("\nTHE MAZE HAS NO SOLUTION.\n");
}
// This method determines if a coordinate position is inbounds or not
private boolean inBounds(int r, int c)
{
boolean inBound = false;
if(r >= 0 && c >= 0)
{
if((r + 1 ) < mat.length && (c + 1) < mat[0].length)
inBound = true;
}
return inBound;
}
// This method checks eight possible positions in a counter-clock wise manner
// starting with the (-1,0) position. If a position is found the method returns
// true and the currentMove coordinates are altered to the new position
private boolean getMove() throws IOException
{
boolean canmove = false;
int tempRow = currentMove.getrPos();
int tempCol = currentMove.getcPos();
if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() + 0)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 0] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() + 0;
}
}
if(inBounds((currentMove.getrPos() -1), (currentMove.getcPos() +1)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() + 1)) == true)
{
if(mat[currentMove.getrPos() + 0][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 0;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 1)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() + 1;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 0)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 0] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() + 0;
}
}
if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() + 1][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 1;
tempCol = currentMove.getcPos() - 1;
}
}
if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() + 0][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() + 0;
tempCol = currentMove.getcPos() - 1;
}
}
if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() - 1)) == true)
{
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() - 1] == 'O')
{
canmove = true;
tempRow = currentMove.getrPos() - 1;
tempCol = currentMove.getcPos() - 1;
}
}
currentMove = new Coord(tempRow, tempCol);
return canmove;
}
private void pause() throws IOException
{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String dummy;
System.out.print("\nPress <Enter> to continue ===>> ");
dummy = input.readLine();
}
}
class MyStack<E>
{
private ArrayList<E> data; // stores stack data
private int top; // keeps index of the stack top
public MyStack()
// Initializes an empty array object with references of private variable data objects.
{
data = new ArrayList<E>();
top = -1;
}
public boolean isEmpty()
// Returns true if data is empty, false otherwise
{
return top == -1;
}
public void push (E x)
// Adds variable x to the top of the stack
{
data.add(x);
top++;
}
public E pop()
// Returns and removes the top element from the stack
{
int temp = top;
top--;
return data.remove(temp);
}
public E peek()
// Returns the top element from the stack without removal
{
return data.get(top);
}
}
LinkBack URL
About LinkBacks
BackTracking in a maze
Reply With Quote
Related threads:
