Skip to content

Commit efb66e3

Browse files
deep20jainpivovarit
deep20jain
authored and
pivovarit
committed
Bael 1299 - Maze Solver - [email protected] (eugenp#3537)
* Maze solver using DFS * Adding BFS maze solver * Fixing formatting
1 parent 5a34de4 commit efb66e3

7 files changed

Lines changed: 340 additions & 0 deletions

File tree

‎algorithms/src/main/java/com/baeldung/algorithms/maze/solver/BFSMazeSolver.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.baeldung.algorithms.maze.solver;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
public class BFSMazeSolver {
9+
private static final int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
10+
11+
public List<Coordinate> solve(Maze maze) {
12+
LinkedList<Coordinate> nextToVisit = new LinkedList<>();
13+
Coordinate start = maze.getEntry();
14+
nextToVisit.add(start);
15+
16+
while (!nextToVisit.isEmpty()) {
17+
Coordinate cur = nextToVisit.remove();
18+
19+
if (!maze.isValidLocation(cur.getX(), cur.getY()) || maze.isExplored(cur.getX(), cur.getY())) {
20+
continue;
21+
}
22+
23+
if (maze.isWall(cur.getX(), cur.getY())) {
24+
maze.setVisited(cur.getX(), cur.getY(), true);
25+
continue;
26+
}
27+
28+
if (maze.isExit(cur.getX(), cur.getY())) {
29+
return backtrackPath(cur);
30+
}
31+
32+
for (int[] direction : DIRECTIONS) {
33+
Coordinate coordinate = new Coordinate(cur.getX() + direction[0], cur.getY() + direction[1], cur);
34+
nextToVisit.add(coordinate);
35+
maze.setVisited(cur.getX(), cur.getY(), true);
36+
}
37+
}
38+
return Collections.emptyList();
39+
}
40+
41+
private List<Coordinate> backtrackPath(Coordinate cur) {
42+
List<Coordinate> path = new ArrayList<>();
43+
Coordinate iter = cur;
44+
45+
while (iter != null) {
46+
path.add(iter);
47+
iter = iter.parent;
48+
}
49+
50+
return path;
51+
}
52+
}

‎algorithms/src/main/java/com/baeldung/algorithms/maze/solver/Coordinate.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.baeldung.algorithms.maze.solver;
2+
3+
public class Coordinate {
4+
int x;
5+
int y;
6+
Coordinate parent;
7+
8+
public Coordinate(int x, int y) {
9+
this.x = x;
10+
this.y = y;
11+
this.parent = null;
12+
}
13+
14+
public Coordinate(int x, int y, Coordinate parent) {
15+
this.x = x;
16+
this.y = y;
17+
this.parent = parent;
18+
}
19+
20+
int getX() {
21+
return x;
22+
}
23+
24+
int getY() {
25+
return y;
26+
}
27+
28+
Coordinate getParent() {
29+
return parent;
30+
}
31+
}

‎algorithms/src/main/java/com/baeldung/algorithms/maze/solver/DFSMazeSolver.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.baeldung.algorithms.maze.solver;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
public class DFSMazeSolver {
8+
private static final int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
9+
10+
public List<Coordinate> solve(Maze maze) {
11+
List<Coordinate> path = new ArrayList<>();
12+
if (explore(maze, maze.getEntry()
13+
.getX(),
14+
maze.getEntry()
15+
.getY(),
16+
path)) {
17+
return path;
18+
}
19+
return Collections.emptyList();
20+
}
21+
22+
private boolean explore(Maze maze, int row, int col, List<Coordinate> path) {
23+
if (!maze.isValidLocation(row, col) || maze.isWall(row, col) || maze.isExplored(row, col)) {
24+
return false;
25+
}
26+
27+
path.add(new Coordinate(row, col));
28+
maze.setVisited(row, col, true);
29+
30+
if (maze.isExit(row, col)) {
31+
return true;
32+
}
33+
34+
for (int[] direction : DIRECTIONS) {
35+
Coordinate coordinate = getNextCoordinate(row, col, direction[0], direction[1]);
36+
if (explore(maze, coordinate.getX(), coordinate.getY(), path)) {
37+
return true;
38+
}
39+
}
40+
41+
path.remove(path.size() - 1);
42+
return false;
43+
}
44+
45+
private Coordinate getNextCoordinate(int row, int col, int i, int j) {
46+
return new Coordinate(row + i, col + j);
47+
}
48+
}

‎algorithms/src/main/java/com/baeldung/algorithms/maze/solver/Maze.java‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
package com.baeldung.algorithms.maze.solver;
2+
3+
import java.io.File;
4+
import java.io.FileNotFoundException;
5+
import java.util.Arrays;
6+
import java.util.List;
7+
import java.util.Scanner;
8+
9+
public class Maze {
10+
private static final int ROAD = 0;
11+
private static final int WALL = 1;
12+
private static final int START = 2;
13+
private static final int EXIT = 3;
14+
private static final int PATH = 4;
15+
16+
private int[][] maze;
17+
private boolean[][] visited;
18+
private Coordinate start;
19+
private Coordinate end;
20+
21+
public Maze(File maze) throws FileNotFoundException {
22+
String fileText = "";
23+
try (Scanner input = new Scanner(maze)) {
24+
while (input.hasNextLine()) {
25+
fileText += input.nextLine() + "\n";
26+
}
27+
}
28+
initializeMaze(fileText);
29+
}
30+
31+
private void initializeMaze(String text) {
32+
if (text == null || (text = text.trim()).length() == 0) {
33+
throw new IllegalArgumentException("empty lines data");
34+
}
35+
36+
String[] lines = text.split("[\r]?\n");
37+
maze = new int[lines.length][lines[0].length()];
38+
visited = new boolean[lines.length][lines[0].length()];
39+
40+
for (int row = 0; row < getHeight(); row++) {
41+
if (lines[row].length() != getWidth()) {
42+
throw new IllegalArgumentException("line " + (row + 1) + " wrong length (was " + lines[row].length() + " but should be " + getWidth() + ")");
43+
}
44+
45+
for (int col = 0; col < getWidth(); col++) {
46+
if (lines[row].charAt(col) == '#')
47+
maze[row][col] = WALL;
48+
else if (lines[row].charAt(col) == 'S') {
49+
maze[row][col] = START;
50+
start = new Coordinate(row, col);
51+
} else if (lines[row].charAt(col) == 'E') {
52+
maze[row][col] = EXIT;
53+
end = new Coordinate(row, col);
54+
} else
55+
maze[row][col] = ROAD;
56+
}
57+
}
58+
}
59+
60+
public int getHeight() {
61+
return maze.length;
62+
}
63+
64+
public int getWidth() {
65+
return maze[0].length;
66+
}
67+
68+
public Coordinate getEntry() {
69+
return start;
70+
}
71+
72+
public Coordinate getExit() {
73+
return end;
74+
}
75+
76+
public boolean isExit(int x, int y) {
77+
return x == end.getX() && y == end.getY();
78+
}
79+
80+
public boolean isStart(int x, int y) {
81+
return x == start.getX() && y == start.getY();
82+
}
83+
84+
public boolean isExplored(int row, int col) {
85+
return visited[row][col];
86+
}
87+
88+
public boolean isWall(int row, int col) {
89+
return maze[row][col] == WALL;
90+
}
91+
92+
public void setVisited(int row, int col, boolean value) {
93+
visited[row][col] = value;
94+
}
95+
96+
public boolean isValidLocation(int row, int col) {
97+
if (row < 0 || row >= getHeight() || col < 0 || col >= getWidth()) {
98+
return false;
99+
}
100+
return true;
101+
}
102+
103+
public void printPath(List<Coordinate> path) {
104+
int[][] tempMaze = Arrays.stream(maze)
105+
.map(int[]::clone)
106+
.toArray(int[][]::new);
107+
for (Coordinate coordinate : path) {
108+
if (isStart(coordinate.getX(), coordinate.getY()) || isExit(coordinate.getX(), coordinate.getY())) {
109+
continue;
110+
}
111+
tempMaze[coordinate.getX()][coordinate.getY()] = PATH;
112+
}
113+
System.out.println(toString(tempMaze));
114+
}
115+
116+
public String toString(int[][] maze) {
117+
StringBuilder result = new StringBuilder(getWidth() * (getHeight() + 1));
118+
for (int row = 0; row < getHeight(); row++) {
119+
for (int col = 0; col < getWidth(); col++) {
120+
if (maze[row][col] == ROAD) {
121+
result.append(' ');
122+
} else if (maze[row][col] == WALL) {
123+
result.append('#');
124+
} else if (maze[row][col] == START) {
125+
result.append('S');
126+
} else if (maze[row][col] == EXIT) {
127+
result.append('E');
128+
} else {
129+
result.append('.');
130+
}
131+
}
132+
result.append('\n');
133+
}
134+
return result.toString();
135+
}
136+
137+
public void reset() {
138+
for (int i = 0; i < visited.length; i++)
139+
Arrays.fill(visited[i], false);
140+
}
141+
}

‎algorithms/src/main/java/com/baeldung/algorithms/maze/solver/MazeDriver.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.baeldung.algorithms.maze.solver;
2+
3+
import java.io.File;
4+
import java.util.List;
5+
6+
public class MazeDriver {
7+
public static void main(String[] args) throws Exception {
8+
File maze1 = new File("src/main/resources/maze/maze1.txt");
9+
File maze2 = new File("src/main/resources/maze/maze2.txt");
10+
11+
execute(maze1);
12+
execute(maze2);
13+
}
14+
15+
private static void execute(File file) throws Exception {
16+
Maze maze = new Maze(file);
17+
dfs(maze);
18+
bfs(maze);
19+
}
20+
21+
private static void bfs(Maze maze) {
22+
BFSMazeSolver bfs = new BFSMazeSolver();
23+
List<Coordinate> path = bfs.solve(maze);
24+
maze.printPath(path);
25+
maze.reset();
26+
}
27+
28+
private static void dfs(Maze maze) {
29+
DFSMazeSolver dfs = new DFSMazeSolver();
30+
List<Coordinate> path = dfs.solve(maze);
31+
maze.printPath(path);
32+
maze.reset();
33+
}
34+
}

‎algorithms/src/main/resources/maze/maze1.txt‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
S ########
2+
# #
3+
# ### ## #
4+
# # # #
5+
# # # # #
6+
# ## #####
7+
# # #
8+
# # # # #
9+
##### ####
10+
# # E
11+
# # # #
12+
##########

‎algorithms/src/main/resources/maze/maze2.txt‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
S ##########################
2+
# # # #
3+
# # #### ############### #
4+
# # # # # #
5+
# # #### # # ###############
6+
# # # # # # #
7+
# # # #### ### ########### #
8+
# # # # # #
9+
# ################## #
10+
######### # # # # #
11+
# # #### # ####### # #
12+
# # ### ### # # # # #
13+
# # ## # ##### # #
14+
##### ####### # # # # #
15+
# # ## ## #### # #
16+
# ##### ####### # #
17+
# # ############
18+
####### ######### # #
19+
# # ######## #
20+
# ####### ###### ## # E
21+
# # # ## #
22+
############################

0 commit comments

Comments
 (0)