如何使用C#找到骑士到达目的地所需的最少步数？
我们必须让骑士覆盖棋盘的所有单元格，并且它只能移动到一个单元格一次。
有两种方法可以完成骑士的移动-第一种是骑士从它开始的位置离开单元格，因此它可以从它开始的位置移动并形成一个循环，这称为闭合巡回赛，骑士在其他任何地方完成的第二次比赛，这称为公开巡回赛。如果移动在棋盘内并且该单元格尚未被占用，则该移动是有效的。我们将使所有未占用单元格的值等于-1。
示例
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class KnightWalkProblem{
public class cell{
public int x, y;
public int dis;
public cell(int x, int y, int dis){
this.x= x;
this.y= y;
this.dis= dis;
}
}
static bool isInside(int x, int y, int N){
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
public int minStepToReachTarget(int[] knightPos, int[] targetPos, int N){
int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
Queue q = new Queue| ();
q.Enqueue(new cell(knightPos[0], knightPos[1], 0));
cell t;
int x, y;
bool[,] visit = new bool[N + 1, N + 1];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visit[i, j] = false;
visit[knightPos[0], knightPos[1]] = true;
while (q.Count != 0){
t = q.Peek();
q.Dequeue();
if (t.x == targetPos[0] &&t.y== targetPos[1])
return t.dis;
for (int i = 0; i < 8; i++){
x =t.x+ dx[i];
y =t.y+ dy[i];
if (isInside(x, y, N) && !visit[x, y]){
visit[x, y] = true;
q.Enqueue(new cell(x, y,t.dis+ 1));
}
}
}
return int.MaxValue;
}
}
class Program{
static void Main(string[] args){
KnightWalkProblem kn = new KnightWalkProblem();
int N = 30;
int[] knightPos = { 1, 1 };
int[] targetPos = { 30, 30 };
Console.WriteLine(
kn.minStepToReachTarget(
knightPos,
targetPos, N));
}
}
} | | 输出结果20