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