সি# ব্যবহার করে গন্তব্যে পৌঁছানোর জন্য নাইটের প্রয়োজনীয় ন্যূনতম সংখ্যক পদক্ষেপগুলি কীভাবে খুঁজে পাবেন?

আমাদের বোর্ডের সমস্ত কক্ষকে নাইট কভার করতে হবে এবং এটি শুধুমাত্র একবার একটি কক্ষে যেতে পারে৷

নাইট মুভ শেষ করার দুটি উপায় হতে পারে - প্রথমটি যেখানে নাইটটি সেল থেকে এক নাইট দূরে সরে যায় যেখান থেকে এটি শুরু হয়েছিল, তাই এটি যে অবস্থান থেকে শুরু হয়েছিল সেখানে গিয়ে একটি লুপ তৈরি করতে পারে, একে বন্ধ বলা হয় সফর, দ্বিতীয় যেটিতে নাইট অন্য কোথাও শেষ করে, একে ওপেন ট্যুর বলা হয়। একটি সরানো বৈধ যদি এটি দাবাবোর্ডের ভিতরে থাকে এবং যদি সেলটি ইতিমধ্যেই দখল করা না থাকে৷ আমরা সমস্ত অব্যক্ত ঘরের মান -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