611.Knight Shortest Path

1.Description(Medium)

Given a knight in a chessboard (a binary matrix with0as empty and1as barrier) with asourceposition, find the shortest path to adestinationposition, return the length of the route. Return-1if knight can not reached.

国际象棋棋盘中骑士只能走对角线。

Notice

source and destination must be empty. Knight can not enter the barrier.

Clarification

If the knight is at (x,y), he can get to the following positions in one step:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

Example

[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 2

[[0,1,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 6

[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return -1

2.Code

即BFS找了几层找到了destination

所以加一个size记录当前level,每次遍历完当前level+1；

记得每次走到一个点就把0变成1，因为这样可以避免走重复的路。

class Point {
      public int x, y;
      public Point() { x = 0; y = 0; }
      public Point(int a, int b) { x = a; y = b; }
}

public class Solution {
     /**
     * @param grid a chessboard included 0 (false) and 1 (true)
     * @param source, destination a point
     * @return the shortest path 
     */
    public int m,n;
    public int[] deltaX={2,2,-2,-2,1,1,-1,-1};
    public int[] deltaY={1,-1,1,-1,2,-2,2,-2};

    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        if(grid==null || grid.length==0 || grid[0].length==0){
            return -1;
        }
        m=grid.length;
        n=grid[0].length;

        Queue<Point> queue=new LinkedList<Point>();
        queue.offer(source);
        int step=0;

        while(!queue.isEmpty()){
            //use size to store level(step)
            int size=queue.size();
            for(int i=0;i<size;i++){

                Point current=queue.poll();
                if(current.x==destination.x && current.y==destination.y){
                    return step;
                }

                //loop to find its neighbor which can reachable
                for(int direction=0;direction<8;direction++){
                    Point neighbor=new Point(current.x+deltaX[direction],current.y+deltaY[direction]);
                    //check it if it can reachable
                    if(!inBound(neighbor,grid)){
                        continue;
                    }
                    queue.offer(neighbor);
                    //Make it not accessible
                    grid[neighbor.x][neighbor.y]=true;
                }                
            }
            // every level to add 1 step.
            step++;
        }
        return -1;        
    }

    public boolean inBound(Point point,boolean[][] grid){
        if(point.x<0 || point.x>=m){
            return false;
        }
        if(point.y<0 || point.y>=n){
            return false;
        }
        return (grid[point.x][point.y]==false);
    }

}

如果此题grid中没有障碍，则不需要那个判断inBound

因为是计算步数，所以要加上size来记录step数

以下是C代码：http://www.cnblogs.com/hfc-xx/p/4668619.html

using namespace std;

int fx[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
int vis[50][50];
int sx,sy,ex,ey;

struct zc
{
    int x,y,step;
};

int check(zc t)
{
    if(t.x<1||t.x>8||t.y<1||t.y>8)return 0;
    return 1;
}

int bfs()
{
    zc t,p;
    t.x=sx;
    t.y=sy;
    t.step=0;
    queue<zc>Q;
    Q.push(t);
    while(!Q.empty())
    {
        t=Q.front();
        Q.pop();
        if(t.x==ex&&t.y==ey)return t.step;
        for(int i=0;i<8;i++)
        {
            p.x=t.x+fx[i][0];
            p.y=t.y+fx[i][1];
            p.step=t.step+1;
            if(check(p)&&!vis[p.x][p.y])
            {
                Q.push(p);
                vis[p.x][p.y]=1;
            }
        }
    }
    return -1;
}