مسئله‌ی تاریخچه‌ی جدول

مسئله

    جدولی با 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) نیز برای یافتن کوتاهترین مسیر استفاده کرد.