جلسهی 36: پروژه: حلکنندهی ماز Project: Maze Solver
یک حلکنندهی ماز متنی را در چهار گام میسازیم: تجزیهی ورودی، بررسی دسترسیپذیری، طول کوتاهترین مسیر با BFS و در پایان رسم مسیر روی نقشه.
در این جلسه یاد میگیری
- یک ورودی متنی را به یک ساختار شبکهای قابلپردازش تبدیل کنید.
- شبکه را بهعنوان گراف ضمنی (
implicit graph) پیمایش کنید. - با
BFSکوتاهترین مسیر را پیدا و باparentبازسازی کنید. - کد را به تابعهای کوچک و قابلآزمون تقسیم کنید.
درس
قالب ماز: خطبهخط تا 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) در زمان و حافظه است.
مثالهای این جلسه
- مثال پایتون در پایتون: S.#
- مثال حلقه for در پایتون: for r, row in enumerate(grid):
- مثال لیست در پایتون: MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]
چالشها
- Step 1: Parse the Maze (آسان)
- Step 2: Reachability (متوسط)
- Step 3: Shortest Path Length (متوسط)
- Step 4: Draw the Path (سخت)
بیشتر بخوان
- پایتون چیست؟ تاریخچه، کاربردها و راه شروع
- حلقه for در پایتون: آموزش کامل با range و مثال
- لیست در پایتون: آموزش کامل list با مثال، متدها و نکتهها
← جلسهی 35: درهمسازی و گرافها جلسهی 37: ایتریتورها و ژنراتورها →