পাইথনে গোলপথে পৌঁছানোর ন্যূনতম পথ খুঁজে বের করার প্রোগ্রাম

আমাদের একটি গ্রিড দেওয়া আছে যেতে সেলগুলোতে বিভিন্ন চিহ্ন থাকে যেমন 'X', 'O', '*' এবং '#' এবং এই চিহ্নগুলোর বিভিন্ন অর্থ আছে:

'#' হলো গোল সেল যেখানে আমরা যেতে চাই।
'O' হলো ফ্রি সেল যার মাধ্যমে আমরা গোল সেলে যেতে পারি।
'*' হলো গ্রিডে আমাদের বর্তমান পজিশন।
'X' হলো ব্লকড সেল যার মাধ্যমে যাওয়া যায় না।

আমাদের বর্তমান পজিশন থেকে গোল সেলে পৌঁছাতে কতটুকু মুভ লাগে সেটা বের করতে হবে। যদি গোল erreich্য না হয়, তবে -1 রিটার্ন করুন। গ্রিডটি ইনপুট হিসেবে দেওয়া থাকবে।

উদাহরণস্বরূপ, ইনপুট গ্রিড:

X	X	O	X
X	X	*	X
X	#	O	X
X	X	X	X

হলে আউটপুট হবে 2।

সমাধানের ধাপসমূহ (BFS)

m := grid-এর রো সংখ্যা, n := grid-এর কলাম সংখ্যা
grid-এ '*' খুঁজে বের করুন
ans := 0, queue := [(i, j)]
grid[i][j] := 'X'
queue খালি না হওয়া পর্যন্ত লুপ চালান:
- ans += 1
- newq := []
- queue-এর প্রতিটি (i, j) এর জন্য:
  - (i-1,j), (i,j-1), (i,j+1), (i+1,j) চেক করুন:
    - যদি ভ্যালিড পজিশন এবং 'X' না হয়, তবে:
      - যদি '#' হয়, তবে ans রিটার্ন করুন
      - newq-এ যোগ করুন এবং grid[ii][jj] := 'X'
- queue := newq
-1 রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "*":
                break
        else:
            continue
        break
    ans = 0
    queue = [(i, j)]
    grid[i][j] = "X"
    while queue:
        ans += 1
        newq = []
        for i, j in queue:
            for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
                    if grid[ii][jj] == "#":
                        return ans
                    newq.append((ii, jj))
                    grid[ii][jj] = "X"
        queue = newq
    return -1

print(solve([['X', 'X', 'O', 'X'],
             ['X', 'X', '*', 'X'],
             ['X', '#', 'O', 'X'],
             ['X', 'X', 'X', 'X']]))

ইনপুট

[['X', 'X', 'O', 'X'], ['X', 'X', '*', 'X'], ['X', '#', 'O', 'X'], ['X', 'X', 'X', 'X']]