> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/611.knight-shortest-path.md).

# 611.Knight Shortest Path

## 1.Description(Medium)

Given a knight in a chessboard (a binary matrix with`0`as empty and`1`as barrier) with a`source`position, find the shortest path to a`destination`position, return the length of the route.\
Return`-1`if 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;
}
```