# 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/611.knight-shortest-path.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.