এক ২D মেজ গ্রিড: ০=খালি পথ, ১=উত্তাল। [0,0] থেকে [R-1, C-1] পর্যন্ত যাওয়ার ন্যূনতম স্টেপ (সেল সংখ্যা) বের করতে হবে। না পেলে -1।
উদাহরণ: [[0,0,0],[1,0,0],[1,0,0]] → আউটপুট 5।
BFS সমাধান (শর্টেস্ট পথ অন ওয়েটেড গ্রাফ)
- কিউতে
(row, col, distance)স্টোর করুন। - ভিজিটেড সেলকে ১ করে মার্ক করুন (ভিজিটেড সেট আলাদা রাখা যাবে)।
- ৪ ডিরেকশন এক্সপ্লোর করুন।
- ডেস্টিনেশন পাওয়া গেলে ডিস্ট্যান্স রিটার্ন।
পাইথন কোড
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
q = [(0, 0, 1)] if not A[0][0] else []
A[0][0] = 1 # ভিজিটেড মার্ক
for r, c, d in q:
if (r, c) == (R-1, C-1):
return d
for x, y in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
A[x][y] = 1
q.append((x, y, d+1))
return -1
ob = Solution()
grid = [[0,0,0], [1,0,0], [1,0,0]]
print(ob.solve(grid)) # 5
টাইম কমপ্লেক্সিটি: O(R×C), স্পেস: O(R×C)। স্ট্যান্ডার্ড BFS শর্টেস্ট পথ অ্যালগরিদম।
