جستجوی اول عمق

مسئله

برخی از نقاط روستای برره در حمله‌ی دشمن فرضی آتش گرفته‌اند! این آتش رفته رفته گسترش پیدا کرده و به نقاط دیگر نیز سرایت می‌کند. خرزو خان که تنها بازمانده‌ی روستا در نبرد با دشمن فرضی است، تلاش می‌کند خود را برای نجات به تنها هلیکوپتر روستا برساند.

روستا را به صورت شبکه‌ای با ابعاد $ n \times m $ در نظر بگیرد که برخی خانه‌های آن در آغاز آتش گرفته‌اند و اگر خانه‌ای در زمان $x$ آتش گرفته باشد، هشت خانه‌ی مجاور آن در زمان $ x + k$ آتش خواهند گرفت و هرگز خاموش نمی‌شوند. حال اگر خرزو خان در نقطه‌ی $s$ شبکه باشد، می‌تواند در هر ثانیه به یکی از چهار خانه‌ی مجاور بالا، پایین، راست یا چپ خود برود و تلاش کند به نقطه‌ی $t$ که هلیکوپتر در آن قرار دارد برسد.

الگوریتم جستجوی اول عمق (Depth First Search - DFS) الگوریتمی مشابه الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف است. این دو الگوریتم خواص و کاربردهای مشترک بسیاری دارند و تفاوت اصلی در این است که در هر تکرار الگوریتم DFS تنها یکی از گره‌های مجاور گره پردازش شده برای مرحله‌ی بعد انتخاب می‌شود. به این ترتیب، الگوریتم DFS به جای صف از یک پشته برای مشخص کردن مسیر پیمایش استفاده می‌کند.

الگوریتم DFS با فرض انتخاب گره مبدأ به عنوان گره جاری از مراحل زیر تشکیل یافته است: