จะค้นหาจำนวนขั้นตอนขั้นต่ำที่อัศวินต้องการเพื่อไปยังจุดหมายปลายทางโดยใช้ 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<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