如何使用 C# 找到骑士到达目的地所需的最少步数?
csharpserver side programmingprogramming更新于 2025/4/17 3:37:17
我们必须让骑士覆盖棋盘的所有单元格，并且它只能移动到一个单元格一次。
有两种方法可以完成骑士的移动 - 第一种是骑士距离它开始的单元格只有一步之遥，因此它可以移动到它开始的位置并形成一个循环，这称为封闭的巡回，第二种是骑士在其他任何地方结束，这称为开放的巡回。如果移动在棋盘内并且单元格尚未被占用，则移动有效。我们将使所有未占用单元格的值等于 -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<cell> q = new Queue<cell>();
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
