جدولی با n سطر و m ستون در نظر بگیرید. در تمام خانه‌های این جدول عدد 0 نوشته شده است. در ابتدای کار حامد در خانه‌ای از جدول ایستاده است. او عدد این خانه را پاک می‌کند و عدد 1 را به جای آن می‌نویسد. حامد شروع به حرکت می‌کند و در هر ثانیه یک خانه به بالا، راست، پایین یا چپ می‌رود. او با وارد شدن به هر خانه، عدد نوشته شده در خانه را پاک می‌کند و عددی یک واحد بزرگتر از آخرین عددی که نوشته است را می‌نویسد و بعد از مدتی متوقف می‌شود. می‌دانیم حامد در انتهای حرکت خود تمام خانه‌های جدول را دیده است.
به شما عکسی از اعداد نوشته شده در جدول داده شده است. آیا حامد اعداد روی جدول را به درستی نوشته است؟
ورودی برنامه
[برگرد بالا]
در سطر اول ورودی عدد T ($ 1 \leq T \leq 100 $) ، تعداد تست‌ها آمده است. پیش از هر تست یک سطر خالی آمده است.
برای هر تست در یک سطر ورودی اعداد n ($ 2 \leq n \leq 50 $) ، تعداد سطرها، و m ($ 2 \leq m \leq 50 $) ، تعداد ستون‌ها، را بخوانید. در n سطر بعدی اعداد نوشته شده در جدول آمده که هر سطر شامل m ستون است. اعداد نوشته شده در جدول نابیشتر از $ 10^9$ هستند.
3
2 2
4 11
7 12
2 2
4 7
10 8
2 3
2 13 11
17 18 8
خروجی برنامه
[برگرد بالا]
به ازای هر تست، ابتدا یک سطر شامل ":Case #x" بنویسید که در آن x نشان‌دهنده شماره تست است، با شروع از 1. در صورتی که حامد در طول مسیر اعداد را به درستی یادداشت کرده است "YES" و در غیر اینصورت "NO" را در یک سطر بنویسید.
Case #1:
YES
Case #2:
NO
Case #3:
NO
منبع: مرحله انتخابی مسابقات برنامه‌نویسی بیان 1393، مسئله تاریخچه جدول (Grid History)
حل مسئله
[برگرد بالا]
تنها اطلاعات در اختیار ما اعدادی هستند که آخرین بار روی هر خانه نوشته شده‌اند. بر اساس این اطلاعات امکان تشخیص مسیر حرکت امکانپذیر نیست. به ویژه آنکه ممکن است مسیر مذکور منحصر به فرد نباشد. به عنوان مثال، خروجی حرکت بر اساس دو دنباله
(1,1) → (1,2) → (2,2) → (1,2) → (2,2) → (2,1)
و
(1,1) → (2,1) → (2,2) → (1,2) → (2,2) → (2,1)
هر دو به یک شکل است. بنابراین در روال حل مساله نباید تلاشی برای تشخیص جزئیات مسیر صورت گیرد.
اعداد جدول ورودی را به صورت مرتب شده در نظر بگیرید که دنباله حاصل با $ A_i $ و خانه متناظر هر $ A_i $ با $ L_i $ مشخص شده‌اند $(i=1,2,3, \cdots, n \times m)$. بر اساس مفاهیم ورودی مسئله، هیچ اطلاعی از حرکت‌های قبل از ورود به خانه $ L_1 $ (حرکت‌های قبل از $A_1$) وجود نداشته و بحث در مورد آنها نیز اهمیتی ندارد (چرا؟)؛ اما مستقل از این حرکت‌ها و این که شروع حرکت از چه خانه‌ای بوده است، باید بتوان مسیری از هر $L_i$ (با مقدار $A_i$) به $L_{i+1}$ (با مقدار $A_{i+1}$) یافت که مقدار عدد خانه‌های مسیر بزرگتر از $A_i$ باشند. اگر جدول ورودی را به صورت یک گراف جهت‌دار (چرا جهت‌دار؟) در نظر بگیریم که از هر خانه به عنوان گره گراف توسط یال‌هایی به خانه‌های مجاور خود متصل هستند، یافتن مسیر از $L_i$ به $L_{i+1}$ تبدیل به یافتن کوتاهترین مسیر در گراف متناظر آن می‌شود. خروجی این مسیریابی می‌تواند یکی از سه حالت زیر باشد:
1- مسیری بین $L_i$ و $L_{i+1}$ وجود ندارد.
2- کوتاهترین مسیر بین $L_i$ و $L_{i+1}$ با طول بزرگتر از $A_{i+1} - A_i $ است.
3- کوتاهترین مسیر بین $L_i$ و $L_{i+1}$ با طول نابیشتر از $A_{i+1} - A_i$ است.
برقرار بودن دو حالت اول به ازای حتی یک جفت $L_i$ و $L_{i+1}$ به معنی نادرست بودن اعداد ثبت شده در جدول بوده و باید خروجی NO چاپ شود. اگر به ازای هر جفت $L_i$ و $L_{i+1}$ حالت سوم برقرار باشد، به معنی درست بودن اعداد جدول بوده و باید خروجی YES چاپ شود.
در پیاده‌سازی الگوریتم ارائه شده باید به دو نکته مهم توجه داشت:
1- خانه‌ای با بزرگترین شماره (خانه بیشینه) همواره باید خانه‌ای با یک واحد کمتر از مقدار بیشینه را در مجاورت خود داشته باشد (چرا؟). بنابراین اگر خانه‌ای با مقدار یک واحد کمتر از خانه بیشینه در جدول وجود نداشته یا در مجاورت آن خانه نباشد، جدول حتما به نادرستی پر شده است. اگر این شرط بررسی نگردد، خروجی نمونه دوم ورودی مسئله YES خواهد شد که نادرست است.
2- اگر شماره خانه‌ای زوج باشد، هر حرکت به چهار خانه مجاور مقدار آن خانه را فرد می‌کند. به همین ترتیب با هر حرکت از خانه با شماره فرد، یک عدد زوج در خانه بعدی نوشته می‌شود. بر اساس این استدلال خانه‌های مجاور نمی‌توانند هر دو زوج یا هر دو فرد باشند. پس شرط لازم درستی جدول (و نه شرط کافی) آن است که هیچ دو خانه مجاور جدول هر دو زوج یا هر دو فرد نباشند. برای اعمال این شرط در الگوریتم نیازی به بررسی برقراری آن به ازای هر خانه به صورت قطعه کد جداگانه نیست؛ بلکه کافی است در زمان محاسبه کوتاهترین مسیر بین دو خانه $L_i$ و $L_{i+1}$ (در صورت وجود) بررسی گردد که مجموع طول کوتاهترین مسیر و مقدار دو خانه (یعنی $L_i+L_{i+1}$) زوج باشد (چرا؟). اگر این شرط بررسی نگردد، خروجی نمونه سوم ورودی مسئله YES خواهد شد که نادرست است.
متناسب با الگوریتم مرتب‌سازی و الگوریتم یافتن کوتاهترین مسیر استفاده شده برای پیاده‌سازی این راهکار، پیچیدگی زمانی اجرای الگوریتم در بدترین شرایط ممکن است از مرتبه‌ای مانند $ O(n^4) $ باشد که مرتبه قابل قبولی به نظر نمی‌رسد. اما با توجه به محدودیت مقادیر n و m (نابیشتر از 50)، الگوریتم حتی با چنین مرتبه‌ای در زمان مطلوبی به جواب می‌رسد. اگرچه امکان پیاده‌سازی الگوریتم با مرتبه پایین‌تر نیز وجود دارد.
نکته: با توجه به اینکه وزن تمامی یال‌ها یکسان است می‌توان از
الگوریتم جستجوی اول سطح (BFS) نیز برای یافتن کوتاهترین مسیر استفاده کرد.