1 Algorithm
This is not Dijkstra's algorithm and that is not breadth-first search either. It's an unweighted brute-force shortest path algorithm. Basically, you generate all possible paths from the source node (top-left cell) to the target node (bottom-right) cell.
On my machine (2.5 GHz) the following maze takes about 300 milliseconds to solve:
int[][] mazePlan = {
{0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0},
{1,1,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
};
2 Coding
You should rename the fields minFoundLen, n and m to something like shortestPathLengthSoFar mazeHeight and mazeWidth, respectively. Also, you do not have to initialize m and n to zero; Java initializes integer fields to zero by default.
Taking into consideration what you do with int[][] path, I suggest you rename it to boolean[][] visited.
System.out.println("shortest path is " + minFoundLen);
It's not funky to print the result of an algorithm to standard output; instead, return the actual result, and let the caller of the algorithm do whatever he/she wants.
You can always store maze and visited in the fields of your object; that way, helper asks only three arguments instead of five.
if(path[x][y]!=0){
return;
}
- There should be one space before and after a binary operator.
- There should be one space before and after a parenthesized expression.
So, combining the two above points you should rather write:
if (path[x][y] != 0) {
return;
}
You should also separate "logical blocks" by a single empty line; like this:
if (maze[x][y] != 0) {
return;
}
if (x == m - 1 && y == n - 1) {
minFoundLen = Math.min(minFoundLen, pathLen);
return;
}
path[x][y] = 1;
helper(maze, x + 1, y, pathLen + 1, path);
helper(maze, x - 1, y, pathLen + 1, path);
helper(maze, x, y + 1, pathLen + 1, path);
helper(maze, x, y - 1, pathLen + 1, path);
path[x][y] = 0;
And don't forget that you should have a space after any comma.
3 Alternative impelmentation
I have gathered all the points and used breadth-first search for solving the maze. That it how it might look:
Maze.java:
import java.awt.Point;
import java.util.List;
import java.util.Objects;
public class Maze {
private static final boolean CELL_OCCUPIED = true;
private final boolean[][] maze;
public Maze(final boolean[][] maze) {
Objects.requireNonNull(maze, "The input maze is null.");
final int numberOfRows = maze.length;
if (numberOfRows == 0) {
throw new IllegalArgumentException("The input maze is empty.");
}
int numberOfColumns = 0;
for (int row = 0; row < maze.length; ++row) {
numberOfColumns = Math.max(numberOfColumns, maze[row].length);
}
this.maze = new boolean[numberOfRows][numberOfColumns];
for (int row = 0; row < numberOfRows; ++row) {
for (int column = 0;
column < Math.min(numberOfColumns, maze[row].length);
column++) {
this.maze[row][column] = maze[row][column];
}
}
}
public int getWidth() {
return maze[0].length;
}
public int getHeight() {
return maze.length;
}
public boolean cellIsFree(final Point p) {
return cellIsFree(p.x, p.y);
}
public boolean cellIsWithinMaze(final Point p) {
return p.x >= 0 && p.x < getWidth() && p.y >= 0 && p.y < getHeight();
}
public boolean cellIsTraversible(final Point p) {
return cellIsWithinMaze(p) && cellIsFree(p);
}
public boolean cellIsFree(final int x, final int y) {
checkXCoordinate(x);
checkYCoordinate(y);
return maze[y][x] != CELL_OCCUPIED;
}
public String withPath(final List<Point> path) {
final char[][] matrix = new char[getHeight()][getWidth()];
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
matrix[i][j] = maze[i][j] ? 'x' : '.';
}
}
for (final Point p : path) {
matrix[p.y][p.x] = 'o';
}
final StringBuilder sb = new StringBuilder();
sb.append(new String(matrix[0]));
for (int i = 1; i < matrix.length; ++i) {
sb.append('\n');
sb.append(new String(matrix[i]));
}
return sb.toString();
}
private void checkXCoordinate(final int x) {
if (x < 0) {
throw new IndexOutOfBoundsException(
"The x-coordinate is negative: " + x + ".");
}
if (x >= maze[0].length) {
throw new IndexOutOfBoundsException(
"The x-coordinate is too large (" + x +
"). The amount of columns in this maze is " +
maze[0].length + ".");
}
}
private void checkYCoordinate(final int y) {
if (y < 0) {
throw new IndexOutOfBoundsException(
"The y-coordinate is negative: " + y + ".");
}
if (y >= maze.length) {
throw new IndexOutOfBoundsException(
"The y-coordinate is too large (" + y +
"). The amount of rows in this maze is " +
maze.length + ".");
}
}
}
MazePathFinder.java:
package review;
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
public class MazePathFinder {
private Maze maze;
private Point source;
private Point target;
private boolean[][] visited;
private Map<Point, Point> parents;
public MazePathFinder() {}
private MazePathFinder(final Maze maze,
final Point source,
final Point target) {
Objects.requireNonNull(maze, "The input maze is null.");
Objects.requireNonNull(source, "The source node is null.");
Objects.requireNonNull(target, "The target node is null.");
this.maze = maze;
this.source = source;
this.target = target;
checkSourceNode();
checkTargetNode();
this.visited = new boolean[maze.getHeight()][maze.getWidth()];
this.parents = new HashMap<>();
this.parents.put(source, null);
}
public List<Point> findPath(final Maze maze,
final Point source,
final Point target) {
return new MazePathFinder(maze, source, target).compute();
}
private List<Point> compute() {
final Queue<Point> queue = new ArrayDeque<>();
final Map<Point, Integer> distances = new HashMap<>();
queue.add(source);
distances.put(source, 0);
while (!queue.isEmpty()) {
// Removes the head of the queue.
final Point current = queue.remove();
if (current.equals(target)) {
return constructPath();
}
for (final Point child : generateChildren(current)) {
if (!parents.containsKey(child)) {
parents.put(child, current);
// Appends 'child' to the end of this queue.
queue.add(child);
}
}
}
// null means that the target node is not reachable
// from the source node.
return null;
}
private List<Point> constructPath() {
Point current = target;
final List<Point> path = new ArrayList<>();
while (current != null) {
path.add(current);
current = parents.get(current);
}
Collections.<Point>reverse(path);
return path;
}
private Iterable<Point> generateChildren(final Point current) {
final Point north = new Point(current.x, current.y - 1);
final Point south = new Point(current.x, current.y + 1);
final Point west = new Point(current.x - 1, current.y);
final Point east = new Point(current.x + 1, current.y);
final List<Point> childList = new ArrayList<>(4);
if (maze.cellIsTraversible(north)) {
childList.add(north);
}
if (maze.cellIsTraversible(south)) {
childList.add(south);
}
if (maze.cellIsTraversible(west)) {
childList.add(west);
}
if (maze.cellIsTraversible(east)) {
childList.add(east);
}
return childList;
}
private void checkSourceNode() {
checkNode(source,
"The source node (" + source + ") is outside the maze. " +
"The width of the maze is " + maze.getWidth() + " and " +
"the height of the maze is " + maze.getHeight() + ".");
if (!maze.cellIsFree(source.x, source.y)) {
throw new IllegalArgumentException(
"The source node (" + source + ") is at a occupied cell.");
}
}
private void checkTargetNode() {
checkNode(target,
"The target node (" + target + ") is outside the maze. " +
"The width of the maze is " + maze.getWidth() + " and " +
"the height of the maze is " + maze.getHeight() + ".");
if (!maze.cellIsFree(target.x, target.y)) {
throw new IllegalArgumentException(
"The target node (" + target + ") is at a occupied cell.");
}
}
private void checkNode(final Point node, final String errorMessage) {
if (node.x < 0
|| node.x >= maze.getWidth()
|| node.y < 0
|| node.y >= maze.getHeight()) {
throw new IllegalArgumentException(errorMessage);
}
}
public static void main(String[] args) {
int[][] mazePlan = {
{0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0},
{1,1,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
};
boolean[][] maze2 = new boolean[mazePlan.length][mazePlan[0].length];
for (int i = 0; i < maze2.length; ++i) {
for (int j = 0; j < maze2[i].length; ++j) {
maze2[i][j] = mazePlan[i][j] > 0;
}
}
final Maze maze = new Maze(maze2);
final Point source = new Point(); // Same as new Point(0, 0):
final Point target = new Point(7, 5);
long startTime = System.nanoTime();
final List<Point> path = new MazePathFinder().findPath(maze,
source,
target);
long endTime = System.nanoTime();
System.out.printf("BFS maze finder in %d milliseconds.\n",
(endTime - startTime) / 1_000_000L);
System.out.println("Shortest path length: " + (path.size() - 1));
System.out.println(maze.withPath(path));
}
}
Hope that helps.
