LintCode 1563 · Shortest path to the destination.java

	// Pure BFS:
	// The algorithm is mainly to master the variant with the number of layers.
	// There are some error-prone points in implementation:
	// Note 1: When not found, return -1;
	// Note 2: When found, return to level directly.
	// Note 3: The starting value of level is 1. It means that the first step has already gone, and the queue I just entered, that is to say, all the queues have passed.
	// Note 4: When you encounter something that works, here is a trick to omit the visited array: Mark the road directly on the original image and it will not work.
	public class Solution {
	/**
	* @param targetMap:
	* @return: nothing
	*/
	public int shortestPath(int[][] grid) {
	// write your code here
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	int m = grid.length, n = grid[0].length;
	int level = bfsWithLevel(0, 0, grid, m, n);
	return level;
	}
	private int bfsWithLevel(int i, int j, int[][] grid, int m, int n) {
	Queue<int[]> queue = new ArrayDeque<>();
	// Set<int[]> visited = new HashSet<>();
	queue.add(new int[]{i, j});
	// visited.add(new int[]{i, j});
	int[] dx = new int[]{1, -1, 0, 0};
	int[] dy = new int[]{0, 0, 1, -1};
	int level = 1;
	while (!queue.isEmpty()) {
	int size = queue.size();
	while (size-- > 0) {
	int[] coordinate = queue.poll();
	for (int k = 0; k < 4; k++) {
	int x = coordinate[0] + dx[k];
	int y = coordinate[1] + dy[k];
	if (!isValid(x, y, m, n) || grid[x][y] == 1) {
	continue;
	}
	if (grid[x][y] == 2) {
	return level;
	}
	queue.add(new int[]{x, y});
	grid[x][y] = 1;
	// visited.add(new int[]{x, y});
	}
	}
	level++;
	}
	return -1;
	}
	private boolean isValid(int x, int y, int m, int n) {
	return (x >= 0 && x < m && y >= 0 && y < n);
	}
	}

view raw LintCode 1563 · Shortest path to the destination.java hosted with ❤ by GitHub