استفاده از الگوریتم های DFS، BFS, A_star در کد مربوط به جابه جایی در ماتریس ( تا 12 شب امشب وقت هست)

---

شرح پروژه

ورودی توابع یک آرایه ۲بعدی از کاراکترهاست که هر عضو آن وضعیت یک کاشی را مشخص می‌کند. هر کاشی می‌تواند دارای یکی از ۵ حالت زیر باشد. . دیوار . جعبه . سنگ . شما . کاشی خالی شما می‌توانید وارد خانه‌ای که کاشی خالی و یا جعبه است شوید. همچنین می‌توانید با حرکت به خانه‌هایی که در آن‌ها سنگ قرار دارد سنگ‌ها را هل دهید اما باید توجه داشته باشید که مسیر سنگ در جهتی که هل می‌دهید مسدود نباشد همچنین اگر دو سنگ پشت سر هم بودند نمی‌توانید آن‌ها را هل دهید. هدف شما این است که با حرکت در کاشی‌های ازاد و هل دادن سنگ‌ها، همه سنگ‌ها را در جعبه‌ها بگذارید. وارد دیوار شدن و هل دادن دو سنگ پشت سر هم باعث باختن شما می‌شود. خروجی تابع شما آرایه‌ای از کاراکترهای r, l, u, d می‌باشد که ترتیب حرکت شما را مشخص می‌کند. که به معنی right, left, up و  down است. این ها تعریف متغیر ها در ماتریس ورودی ما است : Free space -> f Box -> b Agent(you) -> a Stone -> s Wall -> w   این مثالی برای ورودی و خروجی است : ورودی : [ [f, f, b], [a, s, f], [f, f, f] ]   خروجی :  [r, d, r, u]   توضیح : مثلا اینجا، در سمت راست خود یک سنگ داشتیم و خونه ی سمت راست خود سنگ هم خالی بود، پس میتوانیم به راست برویم و سنگ را هول بدهیم و سنگ را زیر خانه ای قرار بدهیم که جعبه است. سپس دیگر نمیتوانیم سنگ را هول بدهیم پس به خانه ی پایین می رویم سپس به راست می رویم. حال در خانه ای هستیم که زیر خانه ای است که سنگ در آن است.. پس با هول دادن سنگ به بالا ( پس حرکت ما بالا یا همان u است )، میتوانیم آن را در جعبه بذاریم.   تصور کنید سنگی در سمت راست ما وجود دارد. اگر به راست (r) حرکت کنیم، سنگ نیز به سمت راست می رود (منظورم این است که می توانیم سنگ را به جلو هل دهیم).
اما برای هل دادن سنگ شرطی وجود دارد:
خانه بعدی باید خالی (f) یا جعبه (b) باشد.
بنابراین اگر خانه بعدی خارج از محدوده ماتریس ورودی باشد یا خانه بعدی دیوار باشد یا خانه بعدی جعبه ای باشد که قبلاً سنگی در آن وجود دارد، ما اجازه نداریم سنگ را در این مسیر هل دهیم.
تصور کنید یک ردیف مانند این داریم: [a, s, f]
در این وضعیت، ما "a" هستیم.
اگر به سمت راست (r) حرکت کنیم، نقشه به این شکل به روز می شود: [f, a, s]   توضیحات کلیدی اضافه :

برای جواب این سوال باید یک فایل zip آپلود کنید که شامل فایل solver.py است.

در فایل solver.py باید توابع زیر پیاده‌سازی شده باشند:

def dfs(board2D): return answer1D

 def bfs(board2D): return answer1D

 def a_star(board2D): return answer1D

در مورد a_star، هرچقدر تابع هیوریستیک بهتر باشد، نمره ی بیشتری میگیریم.

مهارت ها و تخصص های مورد نیاز

---

---