# Lee Algorithm in Java

(1608 Views)

### What is Lee Algorithm?

Lee Algorithm is a possible solution for Maze Routing problems. Lee Algorithm is same as Breadth First Search(BFS), but we keep track of the distance and evaluate the shortest distance among the set of distances.

Lee's algorithm always gives the Optimal Solution for Maze Routing Problems, but it is little slow and also requires considerable amount of memory. ### Lee Algorithm Java Program Implementation:

import java.util.LinkedList; import java.util.Queue; class node { int x, y, distance; node(int x, int y, int dist) { this.x = x; this.y = y; this.distance = dist; } } public class lee { // this should be the row and column length of the matrix entered static int M = 5; static int N = 5; static boolean isValid(int mat[][], boolean visited[][], int row, int col) { return ((row >= 0) && (row < M)) && ((col >= 0) && (col < N)) && (mat[row][col] == 1) && (!visited[row][col]); } private static void bfs(int matrix[][], int i, int j, int x, int y) { int row[] = { -1, 0, 0, 1 }; int col[] = { 0, -1, 1, 0 }; boolean[][] visited = new boolean[M][N]; Queue<node> q = new LinkedList<node>(); visited[i][j] = true; q.add(new node(i, j, 0)); int minimum_distance = Integer.MAX_VALUE; while (!q.isEmpty()) { node node = q.poll(); i = node.x; j = node.y; int dist = node.distance; if (i == x && j == y) { minimum_distance = dist; break; } for (int k = 0; k < 4; k++) { if (isValid(matrix, visited, i + row[k], j + col[k])) { visited[i + row[k]][j + col[k]] = true; node n = new node(i + row[k], j + col[k], dist + 1); q.add(n); } } } if (minimum_distance == Integer.MAX_VALUE) { System.out.print("Destination cannot be reached"); } else { System.out.print("The shortest path has length " + minimum_distance); } } public static void main(String[] args) { int[][] matrix = { { 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1 }, { 1, 1, 0, 0, 0 } }; bfs(matrix, 0, 0, 3, 4); } }

In below algorithm, if we find the shortest distance we print “found" and it’s length, else we print “not found” and also we check the coordinates, if it is valid and has not been visited.