# 骑士达成目标的最低限度步骤

## 使用案列

`(kx,ky) = (1,1) & (tx,ty) = (15,15)`
`Minimum number of moves = 10`
`(kx,ky) = (2,8) & (tx,ty) = (8,4)`
`Minimum number of moves = 4`
`(kx,ky) = (2,8) & (tx,ty) = (8,4)`
`Minimum number of moves = 4`

## 广度优先搜索

### 算法

```1. Define a class that has following data variables:
1. x: to store x-coordinate of the cell.
2. y: to store y-coordinate of the cell.
3. steps: number of steps required to reach that cell starting from co-ordinates of the Knight.
2. Create a BFS queue that stores class objects as nodes.
3. Begin the Iterative BFS traversal.
4. In every step of the iterative traversal, pop a node from the queue. say,the node is front.
5. If the cell at coordinates (front.y, front.x) is the target cell, return the value of front.steps.
1. Else, continue the iterative traversal.```

### 代码

#### C ++程序查找骑士达成目标的最低限度步骤

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// definition of queue node
class Node
{
public:
// y-coordinate
int y;
// x-coordinate
int x;
// number of steps to reach (y,x)
int steps;

// constructor
Node(int i,int j,int moves)
{
y = i;
x = j;
steps = moves;
}
};

// traversal array along rows
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
// traversal array along columns
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};

// BFS to return number of steps required to reach from source to target
int BFS(Node source, Node target, int N)
{
// set to mark a cell as visited
unordered_set <string> visited;
// BFS queue
queue <Node> q;
// push the source node
q.push(source);

// BFS traversal
while(!q.empty())
{
Node front = q.front();
q.pop();

// if target coordinate is reached
if(front.y == target.y && front.x == target.x)
return front.steps;

// traverse all neighbors of current cell
for(int i=0;i<8;i++)
{
int next_y = front.y + dy[i];
int next_x = front.x + dx[i];

// store coordinates of a cell as string
string search = to_string(next_y) + '|' + to_string(next_x);

// move to neighbor cell if it is not visited lies within the N x N chessboard
if(visited.find(search) == visited.end() && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
{
Node next(next_y,next_x,front.steps+1);
q.push(next);
visited.insert(search);
}
}
}
}

int main()
{
// dimensions of the square chessboard
int N = 8;
// coordinates of source & target cell
Node source(2,8,0), target(8,4,-1);
cout<<"Number of steps : "<<BFS(source,target,N)<<endl;
return 0;
}```
`Number of steps : 4`

#### Java程序查找骑士达成目标的最低限度步骤

```import java.util.*;
import java.io.*;

class TutorialCup
{
// definition of queue node
static class Node
{
// y-coordinate
int y;
// x-coordinate
int x;
// number of steps to reach (y,x)
int steps;

// constructor
Node(int i,int j,int moves)
{
y = i;
x = j;
steps = moves;
}
};

// traversal array along rows
static int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
// traversal array along columns
static int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};

// BFS to return number of steps required to reach from source to target
static int BFS(Node source, Node target, int N)
{
// set to mark a cell as visited
HashSet <String> visited = new HashSet<>();
// BFS queue
Queue <Node> q = new LinkedList<>();
// push the source node

// BFS traversal
while(!q.isEmpty())
{
Node front = q.poll();

// if target coordinate is reached
if(front.y == target.y && front.x == target.x)
return front.steps;

// traverse all neighbors of current cell
for(int i=0;i<8;i++)
{
int next_y = front.y + dy[i];
int next_x = front.x + dx[i];

// store coordinates of a cell as string
String search = next_y + "|" + next_x;

// move to neighbor cell if it is not visited lies within the N x N chessboard
if(visited.contains(search) == false && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
{
Node next = new Node(next_y,next_x,front.steps+1);
}
}
}
return 0;
}
public static void main (String[] args)
{
// dimensions of the square chessboard
int N = 8;
// coordinates of source & target cell
Node source = new Node(2,8,0);
Node target = new Node(8,4,-1);
System.out.println("Number of steps : "+BFS(source,target,N));
}
}```
`Number of steps : 4`

### 复杂度分析

1. 时间复杂度：T（n）= O（N ^ 2）
因为我们有一个方矩阵，并且在最坏的情况下。 因此，我们可能必须处理每个单元。 这就是实现二次时间复杂度的方式。
2. 空间复杂度：A（n）= O（N ^ 2）
在这里我们使用了BFS，因此该算法具有多项式空间复杂度。

## 动态编程

### 途径

1. 棋盘是标准的N x N正方形。
2. kx和ky是骑士的坐标。
3. tx和ty是目标单元格的坐标。

1. 例如：（kx，ky）=（3,3）＆（tx，ty）=（6,6）
2. 朝目标迈进只有2步，分别是：
• （3,3）->（4,5）和（3,3）->（5,4）
3. 因此，使用 动态编程, minSteps {（3,3）至（6,6）} = 1 + [minSteps {（4,5）至（6,6）} or minSteps {（5,4）至（6,6）}]

1. 例如：（kx，ky）=（2,4）＆（tx，ty）=（7,4）
2. 朝目标迈进的总共有4个步骤，分别是：
• （2,4）->（4,5）和（2,4）->（4,3），这两个步骤都是等效的
• （2,4）->（3,6）和（2,4）->（3,2），这两个步骤都是等效的
3. 因此，使用 动态编程, minSteps {（2,4）至（7,4）} = 1 + 分钟[minSteps {（2,4）至（4,5）} , minSteps {（2,4）至（3,6）}].

1. 表[abs（kx – tx）] [abs（ky-ty）] =从骑士的位置（kx，ky）到目标位置（tx，ty）的最小步数。
2. 表[abs（kx – tx）] [abs（ky-ty）] = table [abs（ky-ty）] [abs（kx-tx）]。

### 算法

```1. Define the solution for corner cases. i.e. when the knight or target are at 4 corners of the board and difference in their positions are (1,1). The minimum number of moves from source to target is 4. These positions are depicted below:
2. Define the base cases as discussed below:
1. when the Knight & target are at adjacent squares (along the same row/column), minimum number of moves required to reach the destination is 3.
2. when the Knight & target are at adjacent squares but lie diagonally to each other, minimum number of moves required to reach the destinations is 2.
3. when Knight & target are at positions as depicted in the image, minimum number of moves required to reach destination is 1.
4. If the Knight & target are at same position, minimum number of moves required is 0.
3. For any other case, refer Linear Positions & Non-Linear Positions in the approach section.```

### 代码

#### C ++程序查找骑士达成目标的最低限度步骤

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int minStepsRecur(int kx, int ky, int tx, int ty, vector<vector<int>>& table)
{
// when Knight & Target are at same position
if (kx == tx && ky == ty)
return table[0][0];

else
{
// if value in the table has been calculated already
if (table[abs(kx - tx)][abs(ky - ty)] != 0)
return table[abs(kx - tx)][abs(ky - ty)];

// Linear Positions
/* Knight can move to -->2 different squares<-- that goes towards the Target */

// Non-Linear Positions
/* Knight can move to 4 different squares that
goes towards the Target of which -->2 are equivalent<-- */

// For every position of Knight & Target
// there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to.
else
{

int x1, y1, x2, y2;

// the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
// (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
// Their calculations are made accordingly
if (kx <= tx)
{
if (ky <= ty)
{
x1 = kx + 2;
y1 = ky + 1;
x2 = kx + 1;
y2 = ky + 2;
}
else
{
x1 = kx + 2;
y1 = ky - 1;
x2 = kx + 1;
y2 = ky - 2;
}
}

else
{
if (ky <= ty)
{
x1 = kx - 2;
y1 = ky + 1;
x2 = kx - 1;
y2 = ky + 2;
}
else
{
x1 = kx - 2;
y1 = ky - 1;
x2 = kx - 1;
y2 = ky - 2;
}
}

// The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2).
table[abs(kx - tx)][abs(ky - ty)] = 1 + min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table));

// exchanging the coordinates x with y of both knight and target will result in same min moves.
table[abs(ky - ty)][abs(kx - tx)] = table[abs(kx - tx)][abs(ky - ty)];

return table[abs(kx - tx)][abs(ky - ty)];
}
}
}

int minSteps(int kx, int ky, int tx, int ty, int n)
{
// Corner Cases
if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1))
return 4;

else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n))
return 4;

else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1))
return 4;

else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n))
return 4;

else
{
vector <int> row(20,0);
vector <vector<int>> table;

for(int i=0; i<20; i++)
table.push_back(row);

// Base Cases
table[2][1] = 1;
table[1][2] = 1;

table[1][1] = 2;
table[2][0] = 2;
table[0][2] = 2;

table[1][0] = 3;
table[0][1] = 3;

// Linear & Non-Linear positions
return minStepsRecur(kx, ky, tx, ty, table);
}
}

int main()
{
int n = 8;
int kx = 2, ky = 8, tx = 8, ty = 4;

cout<<"Number of steps : "<<minSteps(kx,ky,tx,ty,n)<<endl;
return 0;
}```
`Number of steps : 4`

#### Java程序查找骑士达成目标的最低限度步骤

```import java.util.*;
import java.io.*;

class TutorialCup
{
static int minStepsRecur(int kx, int ky, int tx, int ty, int [][] table)
{
// when Knight & Target are at same position
if (kx == tx && ky == ty)
return table[0][0];

else
{
// if value in the table has been calculated already
if (table[Math.abs(kx - tx)][Math.abs(ky - ty)] != 0)
return table[Math.abs(kx - tx)][Math.abs(ky - ty)];

// Linear Positions
/* Knight can move to -->2 different squares<-- that goes towards the Target */

// Non-Linear Positions
/* Knight can move to 4 different squares that
goes towards the Target of which -->2 are equivalent<-- */

// For every position of Knight & Target
// there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to.
else
{

int x1, y1, x2, y2;

// the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
// (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
// Their calculations are made accordingly
if (kx <= tx)
{
if (ky <= ty)
{
x1 = kx + 2;
y1 = ky + 1;
x2 = kx + 1;
y2 = ky + 2;
}
else
{
x1 = kx + 2;
y1 = ky - 1;
x2 = kx + 1;
y2 = ky - 2;
}
}

else
{
if (ky <= ty)
{
x1 = kx - 2;
y1 = ky + 1;
x2 = kx - 1;
y2 = ky + 2;
}
else
{
x1 = kx - 2;
y1 = ky - 1;
x2 = kx - 1;
y2 = ky - 2;
}
}

// The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2).
table[Math.abs(kx - tx)][Math.abs(ky - ty)] = 1 + Math.min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table));

// exchanging the coordinates x with y of both knight and target will result in same min moves.
table[Math.abs(ky - ty)][Math.abs(kx - tx)] = table[Math.abs(kx - tx)][Math.abs(ky - ty)];

return table[Math.abs(kx - tx)][Math.abs(ky - ty)];
}
}
}

static int minSteps(int kx, int ky, int tx, int ty, int n)
{
// Corner Cases
if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1))
return 4;

else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n))
return 4;

else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1))
return 4;

else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n))
return 4;

else
{
int [][] table = new int[20][20];

// Base Cases
table[2][1] = 1;
table[1][2] = 1;

table[1][1] = 2;
table[2][0] = 2;
table[0][2] = 2;

table[1][0] = 3;
table[0][1] = 3;

// Linear & Non-Linear positions
return minStepsRecur(kx, ky, tx, ty, table);
}
}

public static void main (String[] args)
{
int n = 8;
int kx = 2, ky = 8, tx = 8, ty = 4;

System.out.println("Number of steps : "+minSteps(kx,ky,tx,ty,n));
}
}```
`Number of steps : 4`

### 复杂度分析

1. 时间复杂度：T（n）= O [abs（ （kx-tx）*（ky-ty） )]
因为我们只处理开始和目标单元格形成的子矩阵中的单元格。 因此，即使该解决方案也具有类似于上述解决方案的二次时间复杂度。
2. 空间复杂度：A（n）= O [abs（ （kx-tx）*（ky-ty） )]

1. （kx，ky）=骑士的位置
2. （tx，ty）=目标单元格的位置