خالپشت ها، موجوداتی قابلبرنامهریزی هستند که در جدولهای $n \times n$ زندگی میکنند. در بعضی خانههای این جدولها دیوار وجود دارد و عبور از آنها ممکن نیست.
خالپشت ها دنبالهای از دستورها را دریافت میکنند و آنها را به ترتیب اجرا میکنند. دستورها میتوانند از چهار نوع زیر باشند:
• بالا: خالپشت به خانهی بالایی خود میرود.
• پایین: خالپشت به خانهی پایینی خود میرود.
• چپ: خالپشت به خانهی چپی خود میرود.
• راست: خالپشت به خانهی راستی خود میرود.
درصورتی که اجرای بک دستور، خالپشت را به خارج از جدول یا به خانهای که در آن دیوار است ببرد، خالپشت دستور را اجرا نمیکند و به سراغ دستور بعدی میرود.
با توجه به توضیحات بالا به ۴ سؤال زیر پاسخ دهید:
خیکوله خالپشتی پیداکرده است که در یک جدول $۴ \times ۴$ به شکل روبهرو زندگی میکند. خالپشت در خانهی $A$ قرار دارد و خانههای هاشور خورده، خانههایی هستند که در آنها دیوار است. خیکوله میخواهد دنبالهای با کمترین تعداد دستور به خالپشت بدهد که بعد از اجرای آن خالپشت از همهی خانههای جدول حداقل یکبار عبور کرده باشد. تعداد دستورات این دنباله چند است؟
نازخیکول به خیکوله دو جدول $۳ \times ۳$ به شکل روبهرو میدهد که در هرکدام یک خالپشت در خانهی $A$ وجود دارد. نازخیکول از خیکوله میخواهد، دنبالهای از دستورات با کمترین تعداد دستور را پیدا کند که وقتی هر دو خالپشت آن را اجرا کردند، از همهی خانههای جدول خود حداقل یکبار عبور کنند. تعداد دستورات این دنباله چند است؟
حالا خیکوله به نازخیکول یک جدول $۴ \times ۴$ به شکل روبهرو میدهد و به او میگوید که در این جدول دو خالپشت وجود دارد اما جای خالپشت ها را به نازخیکول نمیگوید. خیکوله از نازخیکول میخواهد، دنبالهای از دستورات با کمترین تعداد دستور پیدا کند که وقتی هر دو خالپشت آن را اجرا کردند، مستقل از اینکه در ابتدا در کجای نقشه بودهاند، در انتها هر دو در یک خانه قرار داشته باشند. تعداد دستورات این دنباله چند است؟
نازخیکول یک خالپشت را در یک جدول $۴ \times ۴$ مخفی کرده است و از خیکوله میخواهد جای آن را پیدا کند. برای این کار خیکوله میتواند در هر مرحله یک مربع $۲ \times ۲$ را مشخص کند و از نازخیکول بپرسد که «آیا خالپشت در این مربع $۲ \times ۲$ قرار دارد؟». با فرض اینکه خالپشت جای خود را در جدول عوض نمیکند، در بدترین حالت خیکوله حداقل چند سؤال باید بپرسد تا بتواند جای خالی خالپشت را تشخیص دهد؟