如何使用C#找到骑士到达目的地所需的最少步数？

Z时代
2024-01-10
分类：综合

我们必须让骑士覆盖棋盘的所有单元格，并且它只能移动到一个单元格一次。

有两种方法可以完成骑士的移动 - 第一种是骑士从它开始的位置离开单元格，因此它可以从它开始的位置移动并形成一个循环，这称为闭合巡回赛，骑士在其他任何地方完成的第二次比赛，这称为公开巡回赛。如果移动在棋盘内并且该单元格尚未被占用，则该移动是有效的。我们将使所有未占用单元格的值等于-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));
      }
   }
}