بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 36: پروژه: حل‌کننده‌ی ماز Project: Maze Solver

یک حل‌کننده‌ی ماز متنی را در چهار گام می‌سازیم: تجزیه‌ی ورودی، بررسی دسترسی‌پذیری، طول کوتاه‌ترین مسیر با BFS و در پایان رسم مسیر روی نقشه.

در این جلسه یاد می‌گیری

درس

قالب ماز: خط‌به‌خط تا end؛ # دیوار، . راه، S شروع و E خروج. همه‌ی خطوط هم‌طول‌اند. هر گام یک برنامه‌ی کامل است و می‌توانید تابع‌های گام قبل را دوباره استفاده کنید.

S.#
..E
end

ماز را به‌صورت لیستی از رشته‌ها نگه دارید: grid[r][c]. موقعیت‌ها را tuple (r, c) بگیرید تا بتوانند کلید dict یا عضو set باشند.

grid = ["S.#", "..E"]
for r, row in enumerate(grid):
    c = row.find("S")
    if c != -1:
        print((r, c))

ترتیب بررسی همسایه‌ها در BFS تعیین می‌کند وقتی چند کوتاه‌ترین مسیر وجود دارد کدام انتخاب شود. در این پروژه ترتیب ثابت است: بالا، پایین، چپ، راست؛ و والد هر خانه اولین خانه‌ای است که آن را کشف کرده.

MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]

پیچیدگی: هر خانه حداکثر یک بار وارد صف می‌شود و چهار همسایه دارد، پس BFS روی ماز R × C از مرتبه‌ی O(R·C) در زمان و حافظه است.

مثال‌های این جلسه

چالش‌ها

  1. Step 1: Parse the Maze (آسان)
  2. Step 2: Reachability (متوسط)
  3. Step 3: Shortest Path Length (متوسط)
  4. Step 4: Draw the Path (سخت)

بیشتر بخوان

← جلسه‌ی 35: درهم‌سازی و گراف‌ها جلسه‌ی 37: ایتریتورها و ژنراتورها →