LintCode 611 Knight Shortest Path

思路

BFS，带level信息的坐标型。每次将一层元素都取出来，然后加入队列的时候将其标记为1（障碍）。

复杂度

时间复杂度O(nm)
空间复杂度O(nm)

代码

/*** Definition for a point.* class Point {* int x;* int y;* Point() { x = 0; y = 0; }* Point(int a, int b) { x = a; y = b; }* }*/public class Solution {
    /*** @param grid: a chessboard included 0 (false) and 1 (true)* @param source: a point* @param destination: a point* @return: the shortest path */public int shortestPath(boolean[][] grid, Point source, Point destination) {
    // write your code hereif (grid.length == 0 || grid[0].length == 0) {
    return -1;}int[] dx = {
    1, 1, 2, 2, -1, -1, -2, -2};int[] dy = {
    2, -2, 1, -1, 2, -2, 1, -1};Queue<Point> queue = new LinkedList<>();queue.offer(source);grid[source.x][source.y] = true;int level = 0;while (!queue.isEmpty()) {
    int size = queue.size();for (int k = 0; k < size; k++) {
    Point cur = queue.poll();if (cur.x == destination.x && cur.y == destination.y) {
    return level;}for (int i = 0; i < 8; i++) {
    Point next = new Point(cur.x + dx[i],cur.y + dy[i]);if (inBound(grid, next) && grid[next.x][next.y] == false) {
    queue.offer(next);grid[next.x][next.y] = true;}}}level++;}return -1;}private boolean inBound(boolean[][] grid, Point next) {
    return 0 <= next.x && next.x < grid.length && 0 <= next.y && next.y < grid[0].length;}
}