পাইথনে মেজ থেকে বের হওয়ার জন্য কম্পাস ব্যবহারের সংখ্যা পর্যাপ্ত কিনা চেক করা

মান लीজিয়ে, আমরা একটি গেম খেলছি যেখানে আমরা একটি মেজে আটকে পড়েছি। আমাদের মেজ থেকে বের হতে হবে। মেজটি একটি n x m ম্যাট্রিক্স হিসেবে উপস্থাপিত হতে পারে, যেখানে n হলো সারির সংখ্যা এবং m হলো কলামের সংখ্যা। ম্যাট্রিক্সের প্রতিটি সেল/উপাদান 'O', 'D', 'S', বা '-' যেকোনো একটি সিম্বল ধারণ করে। 'O' মানে পথ ব্লক করা, 'D' মানে মেজ থেকে বের হওয়ার পথ, 'S' মানে আমাদের শুরুয় অবস্থান, এবং '-' মানে আমরা পথে চলতে পারি। আমরা '-' চিহ্নিত যেকোনো সেল দিয়ে বিনামূল্যে যেতে পারি। এছাড়া у нас একটি কম্পাস আছে যার মাধ্যমে আমরা মেজ থেকে বের হওয়ার পথ ('D' সেল) খুঁজে বের করতে পারি। যখন আমাদের ডায়রেকশন খুঁজতে হয়, তখন আমাদের কম্পাস ব্যবহার করতে হয়। কিন্তু আমরা কম্পাস সর্বোচ্চ k বার ব্যবহার করতে পারি। মেজটি একটি ম্যাট্রিক্স হিসেবে এবং কম্পাস ব্যবহারের সংখ্যা দিয়ে দেওয়া থাকলে, আমাদের খুঁজে বের করতে হবে আমরা কি সেইতত কম্পাস ব্যবহার করে মেজ থেকে বের হতে পারি। যদি সম্ভব হয় তবে True রিটার্ন করবে, অন্যথায় False।

ইনপুট যদি এরকম হয়: grid =

n = 4, m = 11, k = 3; তাহলে আউটপুট হবে True।

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

• path_search() ফাংশন সংজ্ঞায়িত করুন। এটি নেবে: curr_pos, grid, total_rows, total_cols, k, predecessor

  • x := curr_pos-এর x মান

  • y := curr_pos-এর y মান

  • যদি grid[x, y] "*" এর সমান হয়, তবে

    • যদি k ০ এর সমান হয়, তবে True রিটার্ন করুন

    • অন্যথায়, False রিটার্ন করুন

  • অন্যথায়,

    • parent := predecessor[curr_pos]

    • succ_pos := succesor_positions(curr_pos, grid, total_rows, total_cols, parent) থেকে রিটার্ন মান দিয়ে একটি নতুন লিস্ট

    • use_compass := True যদি succ_pos-এর আকার > 1 হয়

    • succ_pos-এ প্রতিটি পজিশনের জন্য,

      • predecessor[position] := curr_pos

      • যদি use_compass নন-জিরো হয়, তবে path_search(position, grid, total_rows, total_cols, k - 1, predecessor)

      • অন্যথায়, path_search(position, grid, total_rows, total_cols, k, predecessor)

• succesor_positions() ফাংশন সংজ্ঞায়িত করুন। এটি নেবে: curr_pos, grid, total_rows, total_cols, parent

  • x := curr_pos-এর x মান

  • y := curr_pos-এর y মান

  • succ_pos := একটি নতুন লিস্ট

  • যদি y > 0, তবে left := x, y - 1; succ_pos-এ left যোগ করুন

  • যদি y < total_cols - 1, তবে right := x, y + 1; succ_pos-এ right যোগ করুন

  • যদি x > 0, তবে up := x - 1, y; succ_pos-এ up যোগ করুন

  • যদি x < total_rows - 1, তবে down := x + 1, y; succ_pos-এ down যোগ করুন

  • succ_pos-এ প্রতিটি পজিশনের জন্য, যদি grid[position[0], pos[1]] "O" না হয় এবং pos parent না হয়, তবে শর্ত পূরণকারী succ_pos-এর উপাদানগুলো রিটার্ন করুন

• এখন নিচের কাজগুলো করুন:

  • curr_pos := একটি খালি পেয়ার

  • প্রতিটি ইন্ডেক্স i, আইটেম row গ্রিডে,

    • প্রতিটি ইন্ডেক্স j, আইটেম element row-এ,

      • যদি element 'S' এর সমান হয়, তবে curr_pos := i, j ধারণকারী একটি নতুন পেয়ার

  • predecessor := একটি নতুন ম্যাপ যেখানে curr_pos := None প্রাথমিকভাবে

  • path_search(curr_pos, grid, n, m, k, predecessor)

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

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
    x, y = curr_pos
    if grid[x][y] == "D":
        if k == 0:
            print('True')
        else:
            print('False')
    else:
        parent = predecessor[curr_pos]
        succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
        use_compass = len(succ_pos) > 1
        for position in succ_pos:
            predecessor[position] = curr_pos
            if use_compass:
                path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
            else:
                path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
    x, y = curr_pos
    succ_pos = []
    if y > 0:
        left = (x, y - 1)
        succ_pos.append(left)
    if y < total_cols - 1:
        right = (x, y + 1)
        succ_pos.append(right)
    if x > 0:
        up = (x - 1, y)
        succ_pos.append(up)
    if x < total_rows - 1:
        down = (x + 1, y)
        succ_pos.append(down)
    return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
    curr_pos = ()
    for i, row in enumerate(grid):
        for j, element in enumerate(row):
            if element == 'S':
                curr_pos = (i, j)
    path_search(curr_pos, grid, n, m, k, predecessor={curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
        ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
        ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
        ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]
solve(grid, 4, 11, 3)

ইনপুট

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
        ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
        ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
        ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']], 4, 11, 3

আউটপুট

True