import java.util.ArrayList;

public class Solver implements MazeSolver {

private static ArrayList<Coordinate> coordinates = new ArrayList<Coordinate>();
public Solver() {
}
@Override
public String[][] solve(String[][] map) {
//creates a 2d array of strings to store the solved map
String[][] str =
new String[map.length][map[0].length];
boolean done = false;
for (int row = 0; row < map.length; row++) {
for (int col = 0; col < map[0].length; col++) {
str[row][col] = map[row][col];
}
}
//Find the start and finish coordinate repectively
Coordinate c1 = findStart(str);
Coordinate c2 = findFinish(str);

int x = 0;

//While loop to keep track of whether of not the maze is solved or not
while (done == false) {

//when the coordinate that marks the position within the array reaches the Finish Coordinate, end
if ((c1.getRow() + 1 == c2.getRow()) && c1.getCol() == c2.getCol()) {
str[c2.getRow()][c2.getCol()] = "RIP";
break;

}

// Check left right up and down for the first available space and moves coordinate to that location while marking its previous location with X
if (isClear(str, c1.getRow() + 1, c1.getCol())) {

str[c1.getRow() + 1][c1.getCol()] = "X";
c1 = new Coordinate(c1.getRow() + 1, c1.getCol());
coordinates.add(c1);
} else if (isClear(str, c1.getRow(), c1.getCol() + 1)) {
str[c1.getRow()][c1.getCol() + 1] = "X";
c1 = new Coordinate(c1.getRow(), c1.getCol() + 1);
coordinates.add(c1);
} else if (isClear(str, c1.getRow(), c1.getCol() - 1)) {
str[c1.getRow()][c1.getCol() - 1] = "X";
c1 = new Coordinate(c1.getRow(), c1.getCol() - 1);
coordinates.add(c1);
} else if (isClear(str, c1.getRow() - 1, c1.getCol())) {
str[c1.getRow() - 1][c1.getCol()] = "X";
c1 = new Coordinate(c1.getRow() - 1, c1.getCol());
coordinates.add(c1);
}

//If the current coordinate is surrounded on all sides by X, W, or D then it has exhausted all available paths and moves back one space, simultaneously changing said space to a D so as not to revisit the spot again.
if ((str[c1.getRow() - 1][c1.getCol()].equals("X")
|| str[c1.getRow() - 1][c1.getCol()].equals("W") || str[c1
.getRow() - 1][c1.getCol()].equals("D"))
&& (str[c1.getRow() + 1][c1.getCol()].equals("X")
|| str[c1.getRow() + 1][c1.getCol()].equals("W") || str[c1
.getRow() + 1][c1.getCol()].equals("D"))
&& (str[c1.getRow()][c1.getCol() - 1].equals("X")
|| str[c1.getRow()][c1.getCol() - 1].equals("W") || str[c1
.getRow()][c1.getCol() - 1].equals("D"))
&& (str[c1.getRow()][c1.getCol() + 1].equals("X")
|| str[c1.getRow()][c1.getCol() + 1].equals("W") || str[c1
.getRow()][c1.getCol() + 1].equals("D"))) {

str[c1.getRow()][c1.getCol()] = "D";
coordinates.remove(coordinates.size() - 1);
c1 = coordinates.get(coordinates.size() - 1);
}

//Counter for x. In the event that the map uses over 500 iterations of the loop, break because its stuck in an infinite loop and wont solve.
x++;
if(x >= 500) {
c1 = findStart(map);
break;
}
}
//Returns solved Array
return str;
}

//finds start coordinate (simple)
public Coordinate findStart(String[][] map) {
Coordinate start = new Coordinate(0, 0);
for (int row = 0; row < map.length; row++) {
for (int col = 0; col < map[0].length; col++) {
if (map[row][col].equals("S")) {
start = new Coordinate(row, col);
}
}
}
return start;
}

//Finds the Finish coordinate (simple)
public Coordinate findFinish(String[][] map) {
Coordinate finish = new Coordinate(0, 0);
for (int row = 0; row < map.length; row++) {
for (int col = 0; col < map[0].length; col++) {
if (map[row][col].equals("F")) {
finish = new Coordinate(row, col);
}
}
}
return finish;
}
//Checks each individual space within the map array. If space contains W, S, F, D, or is out of the array boundaries its not a clear space.
public boolean isClear(String[][] map, int x, int y) {
if (x >= map.length) {
return false;
}
if (x >= map[0].length) {
return false;
}
if (map[x][y].equals("S")) {
return false;
}
if (map[x][y].equals("D")) {
return false;
}
if (map[x][y].equals("W")) {
return false;
}
return true;
}
}

public class Coordinate {
private int row;
private int col;

public Coordinate(int row, int col) {
this.row = row;
this.col = col;
}

public int getRow() {
return row;
}

public int getCol() {
return col;
}
public String toString() {
return "Coordinate [row=" + row + ", col=" + col + "]";
}

}

public interface MazeSolver {
public String[][] solve(String[][] map);
}

public static void main(String[] args) {
Solver s1 = new Solver();

String[][] map = {
{ "W", "S", "W", "W", "W", "W", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "", "", "", "", "", "" , "W"},
{ "W", "", "W", "", "W", "W", "W", "W", "W", "", "W" },
{ "W", "", "W", "", "W", "", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "W", "W", "", "W", "W", "", "W" },
{ "W", "", "W", "", "W", "", "", "W", "W", "" , "W"},
{ "W", "", "W", "", "", "", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "W", "W", "W", "W", "W", "" , "W"},
{ "W", "", "", "", "W", "", "", "", "W", "" , "W"},
{ "W", "W", "W", "W", "W", "W", "W", "W", "W", "F" , "W"} };
for (int i = 0; i < s1.solve(map).length; i++) {
for (int j = 0; j < s1.solve(map)[0].length; j++) {
System.out.printf("%3s", s1.solve(map)[i][j]);
}
System.out.println();
}
}

public class RecursiveMazeSolver implements MazeSolver
{

private MazeWalker walker;
public String[][] solve(String[][] map)
{
walker = new MazeWalker(map);
solve();
return map;
}
private void solve()
{
for(Direction d : Direction.values())
{

solve(d);


}

}
private void solve(Direction d)
{
if(!walker.isDone() && walker.canMove(d) && !walker.isVisited(d))
{
walker.move(d);
solve();
if(!walker.isDone())
{
walker.backUp(d.getOpposite());

}


}
}

public static void main(String[] args)
{
MazeSolver s1 = new RecursiveMazeSolver();

String[][] map = {
{ "W", "S", "W", "W", "W", "W", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "", "", "", "", "", "" , "W"},
{ "W", "", "W", "", "W", "W", "W", "W", "W", "", "W" },
{ "W", "", "W", "", "W", "", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "W", "W", "", "W", "W", "", "W" },
{ "W", "", "W", "", "W", "", "", "W", "W", "" , "W"},
{ "W", "", "W", "", "", "", "W", "W", "W", "" , "W"},
{ "W", "", "W", "", "W", "W", "W", "W", "W", "" , "W"},
{ "W", "", "", "", "W", "", "", "", "W", "" , "W"},
{ "W", "W", "W", "W", "W", "W", "W", "W", "W", "F" , "W"} };

map = s1.solve(map);
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.printf("%3s", map[i][j]);
}
System.out.println();
}
}


}

public class MazeWalker {
private String[][] maze;
private int currR, currC;
private static final String START = "S";
private static final String FINISH = "F";
private static final String WALL = "W";
private static final String VISITED = "D";
private static final String PATH = "X";
private static final String OPEN = "";

public MazeWalker(String[][] maze)
{
this.maze = maze;
findStart();

}

public boolean canMove(Direction d)
{
int dR, dC;

dR = currR + deltaRow(d);
dC = currC + deltaCol(d);


return dR >= 0 && dR < maze.length && dC >= 0 && dC < maze[dR].length && !maze[dR][dC].equals(WALL);

}

public boolean isVisited(Direction d)
{
int r = currR + deltaRow(d);
int c = currC + deltaCol(d);

return canMove(d) && (maze[r][c].equals(VISITED) || maze[r][c].equals(PATH));
}

public boolean isDone()
{
return maze[currR][currC].equals(FINISH);
}

public void backUp(Direction d)
{
if(canMove(d))
{
if(!(maze[currR][currC].equals(START) || maze[currR][currC].equals(FINISH)))
maze[currR][currC] = VISITED;
currR += deltaRow(d);
currC += deltaCol(d);
}

}
public void move(Direction d)
{
//mark path
if(maze[currR][currC].equals(OPEN))
maze[currR][currC] = PATH;

if(canMove(d))
{
currR += deltaRow(d);
currC += deltaCol(d);

}

}



private int deltaRow(Direction d)
{
int delta = 0;
switch(d)
{
case UP:
delta = -1;
break;
case DOWN:
delta = +1;
break;
default:
}

return delta;
}

private int deltaCol(Direction d)
{
int delta = 0;
switch(d)
{
case LEFT:
delta = -1;
break;
case RIGHT:
delta = +1;
break;
default:
}

return delta;
}


private void findStart()
{
for(int i = 0; i < maze.length; i++)
{
for(int j = 0; j < maze[i].length; j++)
{
if(maze[i][j] == START)
{
currR = i; currC = j;
}
}
}
}
}

public enum Direction {
UP,
DOWN,
LEFT,
RIGHT;

private Direction opposite;

static
{
UP.opposite = DOWN;
DOWN.opposite = UP;
LEFT.opposite = RIGHT;
RIGHT.opposite = LEFT;
}

public Direction getOpposite()
{
return opposite;
}
}

package lab8;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

import javax.swing.*;

public class MazeGUI {
String[][] map = new String[10][10];
JPanel labelPanel, startPanel;
JLabel labs;

private void createMaze() {
// creates the maze
final JFrame frame = new JFrame("Zombie Run");
frame.setLayout(new BorderLayout());
final JPanel labelPanel = new JPanel();
labelPanel.setBorder(BorderFactory.createEmptyBorder(2, 2, 2, 2));
labelPanel.setLayout(new GridLayout(10, 10));
JPanel panelss = new JPanel();
final JLabel unsolvable = new JLabel();

for (int row = 0; row < 10; row++) {
for (int cols = 0; cols < 10; cols++) {
final int i = row;
final int j = cols;
final JLabel labs = new JLabel();

// create and set the labels
labs.setSize(new Dimension(50, 50));
labs.setBorder(BorderFactory.createLineBorder(Color.blue));

labs.setBackground(Color.black);
map[row][cols] = "";

mapArray(row, cols, labs);
labs.addMouseListener(new MouseListener() {
boolean clicked = false;

@Override
public void mouseClicked(MouseEvent arg0) {
// the color changes when clicked

if (clicked == true) {
clicked = false;
labs.setBackground(Color.black);
map[i][j] = "";

} else {
clicked = true;
labs.setBackground(Color.cyan);
map[i][j] = "W";

}

}

@Override
public void mouseEntered(MouseEvent e) {
// TODO Auto-generated method stub

}

@Override
public void mouseExited(MouseEvent e) {
// TODO Auto-generated method stub

}

@Override
public void mousePressed(MouseEvent e) {
// TODO Auto-generated method stub

}

@Override
public void mouseReleased(MouseEvent e) {
// TODO Auto-generated method stub

}
});
if (map[i][j].equals("X") || map[i][j].equals("D")) {
labs.setBackground(Color.RED);
}

if (row == 0 || row == 9) {
labs.setBackground(Color.cyan);
map[row][cols] = "W";
}

if (cols == 0 || cols == 9) {
labs.setBackground(Color.cyan);
map[row][cols] = "W";
}

if (row == 0 && cols == 1) {
labs.setBackground(Color.black);
map[row][cols] = "S";
}
if (row == 9 && cols == 8) {
labs.setBackground(Color.black);
map[row][cols] = "F";

}
labs.setOpaque(true);
labelPanel.add(labs);

}

}

startPanel = new JPanel();
JButton runMaze = new JButton("Feed the Zombie");
runMaze.addActionListener(new ActionListener() {
boolean clicked = false;

@Override
public void actionPerformed(ActionEvent arg0) {
// Makes the zombie find the brain
if (clicked == false) {
clicked = true;
Solver solver;
solver = new Solver();
solver.solve(map);
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.printf("%3s", solver.solve(map)[i][j]);
if (solver.solve(map)[9][8].equals("F")) {
unsolvable.setText("UNSOLVABLE MAZE");
frame.pack();
}
}
System.out.println();
labelPanel.validate();
labelPanel.repaint();
}
}

}
});
panelss.add(unsolvable);
runMaze.setBackground(Color.green);
startPanel.add(runMaze);
runMaze.add(labelPanel);
frame.add(labelPanel, BorderLayout.NORTH);
frame.add(startPanel, BorderLayout.SOUTH);
frame.add(panelss, BorderLayout.EAST);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setVisible(true);
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.printf("%3s", map[i][j]);
}
System.out.println();
}
System.out.println();
}

private void mapArray(int row, int cols, JLabel labs) {
// checks the space and inserts string

if (row == 0 || row == 9) {
map[row][cols] = "W";
map[row][cols] = "W";
}
if (cols == 0 || cols == 9) {
map[row][cols] = "W";
map[row][cols] = "W";
}
if (row == 0 && cols == 1) {
map[0][1] = "S";
labs.setText("Start");
}
if (row == 9 && cols == 8) {
map[row][8] = "F";
labs.setText("End");
} else {
map[row][cols] = "";
}
}

public static void main(String[] args) {
// runs the program
MazeGUI c = new MazeGUI();
c.createMaze();
}
};