Chúng ta phải làm cho kỵ sĩ che tất cả các ô của bàn cờ và nó có thể di chuyển đến ô chỉ một lần.
Có thể có hai cách để kết thúc hành động của hiệp sĩ - cách thứ nhất trong đó hiệp sĩ là một hiệp sĩ di chuyển khỏi ô từ nơi nó bắt đầu, vì vậy nó có thể đi đến vị trí từ nơi nó bắt đầu và tạo thành một vòng lặp, điều này được gọi là đóng. chuyến tham quan thứ hai mà hiệp sĩ kết thúc ở bất kỳ nơi nào khác, đây được gọi là chuyến tham quan mở rộng. Một nước đi hợp lệ nếu nó ở bên trong bàn cờ và nếu ô chưa bị chiếm. Chúng tôi sẽ đặt giá trị của tất cả các ô trống bằng -1.
Ví dụ
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));
}
}
}
Đầu ra
20