วิธีหาจำนวนขั้นตอนน้อยที่สุดที่อัศวินต้องใช้เพื่อไปถึงจุดหมายด้วย C#

เราต้องทำให้อัศวินครอบคลุมทุกเซลล์บนกระดานและสามารถย้ายไปยังเซลล์ใดเซลล์หนึ่งได้เพียงครั้งเดียวเท่านั้น

มี 2 วิธีในการจบการเคลื่อนที่ของอัศวิน - วิธีแรกคืออัศวินอยู่ห่างจากเซลล์เริ่มต้นเพียงหนึ่งการเคลื่อนที่ จึงสามารถกลับไปยังตำแหน่งเริ่มต้นและสร้างลูปได้ เรียกว่า Closed Tour วิธีที่สองคืออัศวินจบที่ตำแหน่งอื่น เรียกว่า Open Tour การเคลื่อนที่ถือว่าถูกต้องหากอยู่ภายในกระดานหมากรุกและเซลล์นั้นยังไม่ถูกครอบครอง เราจะกำหนดค่าของเซลล์ว่างทั้งหมดเป็น -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 q = new Queue();
            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