Shortest path in a binary maze

Problem

Given a maze in the form of the binary rectangular matrix. We need to find the shortest path between a given source cell to a destination cell. The path can only be constructed out of cells having value 1 and at any given moment, we can only move one step in one of the four directions.

Analysis

Single-source shortest paths. Given a graph and a source vertex s, support queries of the form Is there a path from s to a given target vertex v? If so, find a shortest such path (one with a minimal number of edges). The classical method for accomplishing this task, called breadth-first search.
– Algorithms 4th Edition, Robert Sedgewick and Kevin Wayne, Princeton University

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package com.alg.graph.bfs;

import java.util.LinkedList;
import java.util.Queue;

public class LeeAlgorithm {
	// move direction
	final static int d[][] = {
			{0,1},  //right
			{1,0},  //down
			{0,-1}, //left
			{-1,0}  //up
	};

	public static int bfs(int[][] maze, Point src, Point dest) {
		int minDist = Integer.MAX_VALUE;

	    if (maze[src.x][src.y] != 1 || maze[dest.x][dest.y] != 1)
	    	return minDist;

		int h = maze.length;
		int w = maze[0].length;
		boolean[][] visited = new boolean[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				visited[i][j] = false;
			}
		}

		Queue<Node> q = new LinkedList<>();
		Node s = new Node(src, 0);
		q.add(s);

		while (!q.isEmpty()) {
			Node curr = q.poll();
			Point pt = curr.pt;
			if (pt.x == dest.x && pt.y == dest.y)
				return curr.dist;
			for (int i = 0; i < 4; i++) {
				int row = pt.x + d[i][0];
				int col = pt.y + d[i][1];
				if (isValid(maze, visited, h, w, row, col)) {
					visited[row][col] = true;
					Node adjCell = new Node(new Point(row, col), curr.dist + 1);
					q.add(adjCell);
				}
			}
		}
		return minDist;
	}

	private static boolean isValid(int[][] maze, boolean[][] visited, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && maze[row][col] == 1 && !visited[row][col];
	}

	public static void main(String[] args) {
		int[][] maze = {
				{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
				{ 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
				{ 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
				{ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
				{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
				{ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
				{ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
				{ 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
				{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
				{ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 }
		};

		int h = maze.length;
		int w = maze[0].length;
		System.out.printf("%d*%d\n", h, w);

		Point source = new Point(0, 0);
		Point dest = new Point(7, 5);
		int dist = bfs(maze, source, dest);

		if (dist != Integer.MAX_VALUE)
			System.out.printf("The shortest path from (%d,%d) to (%d,%d) has length %d\n", source.x, source.y, dest.x,
					dest.y, dist);
		else
			System.out.printf("Shortest path from (%d,%d) to (%d,%d) doesn't exist\n", source.x, source.y, dest.x,
					dest.y);
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static class Node {
		Point pt;
		int dist;

		public Node(Point pt, int dist) {
			this.pt = pt;
			this.dist = dist;
		}
	}
}

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
function Point(x, y) {
  this.x = x;
  this.y = y;
}

function Node(pt,dist) {
  this.pt = pt;
  this.dist = dist;
}

var d = [
  {x: 0, y: 1},
  {x: 1, y: 0},
  {x: 0, y: -1},
  {x: -1, y: 0}
];

function bfs(maze, src, dest) {
  var minDist = -1;
    if (maze[src.x][src.y] != 1 || maze[dest.x][dest.y] != 1)
      return minDist;
  var h = maze.length;
  var w = maze[0].length;
  visited = [];
  for (var i = 0; i < h; i++) {
    visited.push([]);
    for (var j = 0; j < w; j++) {
      visited[i].push(false);
    }
  }
  var queue = [];
  var s = new Node(src, 0);
  queue.push(s);

  while (queue.length>0) {
    var curr = queue.pop();
    var pt = curr.pt;
    if (pt.x == dest.x && pt.y == dest.y)
      return curr.dist;
    for (var i = 0; i < 4; i++) {
      var row = pt.x + d[i].x;
      var col = pt.y + d[i].y;
      if (isValid(maze, visited, h, w, row, col)) {
        visited[row][col] = true;
        var adjCell = new Node(new Point(row, col), curr.dist + 1);
        queue.push(adjCell);
      }
    }
  }
  return minDist;
}

function isValid(maze, visited, width, height, row, col) {
  return (row >= 0) && (row < width) && (col >= 0) && (col < height) && maze[row][col] == 1 && !visited[row][col];
}

var maze = [
    [ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 ],
    [ 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 ],
    [ 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 ],
    [ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 ],
    [ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 ],
    [ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 ],
    [ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 ],
    [ 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 ],
    [ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 ],
    [ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 ]
];

var source = new Point(0, 0);
var dest = new Point(7, 5);
var dist = bfs(maze, source, dest);

if (dist != -1)
  console.log(`The shortest path from (${source.x}, ${source.y}) to (${dest.x}, ${dest.y}) has length ${dist}\n`);
else
  console.log(`Shortest path from ${(source.x, source.y)} to ${(dest.x, dest.y)} does not exist`);

ref