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