পাইথনে চেস টুকরোর প্রতিটি পজিশনে পৌঁছানোর ন্যূনতম মুভ বের করা

মান লিজিয়ে, আমাদের একটি চেসবোর্ড এবং একটি বিশেষ নাইট পিস K আছে, যা বোর্ডের ভেতরে L আকারে মুভ করে। যদি পিসটি (x1, y1) পজিশনে থাকে এবং (x2, y2)-এ মুভ করে, তবে এই মুভমেন্টকে যেন করা যায়: x2 = x1 ± a; y2 = y1 ± b অথবা x2 = x1 ± b; y2 = y1 ± a; যেখানে a এবং b পূর্ণসংখ্যা। আমাদের খুঁজে বের করতে হবে চেসবোর্ডে (0, 0) পজিশন থেকে (n-1, n-1) পজিশনে পৌঁছানোর জন্য সেই চেস পিসের ন্যূনতম মুভ সংখ্যা। যদি কোনো পজিশন অ্যাক্সেসযোগ্য না হয়, তবে এটি -1 চিহ্নিত হবে, অন্যথায় মুভের সংখ্যা রিটার্ন করা হবে। আমরা n-1 লাইন আউটপুট প্রিন্ট করব, যেখানে প্রতিটি লাইন i-এ n-1টি পূর্ণসংখ্যা থাকবে যা প্রতিটি j-এর জন্য পিসের ন্যূনতম মুভ সংখ্যা বর্ণনা করবে।

ইনপুট যদি n = 6 হয়, তবে আউটপুট হবে:

5  4  3  2  5
4 -1  2 -1 -1
3  2 -1 -1 -1
2 -1 -1 -1 -1
5 -1 -1 -1  1

সমাধান পদ্ধতি

• path_search() ফাংশন সংজ্ঞায়িত করুন। এটি নেবে: i, j, n

  • temp_list := (-1, -1) পেয়ার দিয়ে আরম্ভ করা একটি নতুন ম্যাপ

  • queue_positional := (0, 0) পেয়ার দিয়ে আরম্ভ করা একটি নতুন লিস্ট

  • ver := [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]

  • যখন queue_positional-এর আকার > 0,

    • current_element := queue_positional থেকে প্রথম এলিমেন্ট ডিলিট করুন

    • ver-এ প্রতিটি এলিমেন্টের জন্য,

      • x := element[0] + current_element[0]

      • y := element[1] + current_element[1]

      • যদি -1 < x < n এবং -1 < y < n এবং temp_list[x, y] (-1, -1) এর সমান হয়, তবে

        • temp_list[x, y] := current_element

        • queue_positional-এ (x, y) পেয়ার যোগ করুন

        • যদি x == n-1 এবং y == n-1 হয়, তবে

          • count_var := 1

          • যখন temp_list[x,y] != (0, 0),

            • count_var := count_var + 1

            • x, y := temp_list[x,y]

          • count_var রিটার্ন করুন

    • -1 রিটার্ন করুন

  • মেইন ফাংশন থেকে:

    • board := -1 দিয়ে আরম্ভ করা একটি নতুন ম্যাপ

    • i = 1 থেকে n পর্যন্ত,

      • j = 1 থেকে i পর্যন্ত,

        • যদি board[i, j] == -1, তবে

          • board[i, j] := path_search(i, j, n)

          • board[j, i] := board[i, j]

        • যদি (n-1) % i == 0, তবে board[i, i] := (n-1) / i

      • i = 1 থেকে n পর্যন্ত,

        • j = 1 থেকে n-1 পর্যন্ত, print(board[i, j])

        • print(board[i, n-1])

    সোর্স কোড (পাইথন)

    from collections import defaultdict
    
    def path_search(i, j, n):
        temp_list = defaultdict(lambda: (-1,-1))
        queue_positional = [(0, 0)]
        ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
        while len(queue_positional) > 0:
            current_element = queue_positional.pop(0)
            for element in ver:
                x = element[0] + current_element[0]
                y = element[1] + current_element[1]
                if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
                    temp_list[x, y] = current_element
                    queue_positional.append((x, y))
                    if x == n - 1 and y == n - 1:
                        count_var = 1
                        while temp_list[x,y] != (0,0):
                            count_var += 1
                            x, y = temp_list[x,y]
                        return count_var
        return -1
    
    def solve(n):
        board = defaultdict(lambda: -1)
        for i in range(1, n):
            for j in range(1, i):
                if board[i, j] == -1:
                    board[i, j] = path_search(i, j, n)
                    board[j, i] = board[i, j]
            if (n - 1) % i == 0:
                board[i, i] = (n - 1) / i
        for i in range(1, n):
            for j in range(1, n - 1):
                print(int(board[i, j]), end=' ')
            print(int(board[i, n - 1]))
    
    solve(6)

    ইনপুট

    6

    আউটপুট

    5  4  3  2  5
    4 -1  2 -1 -1
    3  2 -1 -1 -1
    2 -1 -1 -1 -1
    5 -1 -1 -1  1