مسیر شبکه

یک جدول $n\times m$ داریم که سطرهای آن از بالا به پایین و ستون‌های آن از چپ به راست شماره‌گذاری شده است و در هر خانه‌ی آن یک عدد طبیعی قرار دارد. از یک خانه‌ی دلخواه شروع می‌کنیم و هر مرحله به یکی از خانه‌های مجاور دیده‌نشده‌ی خود می‌رویم و اعداد خانه‌هایی که رویشان می‌رویم را به ترتیب دیدن یادداشت می‌کنیم. به دنباله‌ای از خانه‌های مجاور که اعداد نوشته‌شده‌ی آن‌ها به صورت دنباله‌ای حسابی درآیند، یک «دنباله‌ی شکری» می‌گوییم؛ هر خانه به تنهایی یک دنباله‌ی شکری است. برای فهم بیشتر به مثال زیر توجه کنید:

در شکل بالا، اگر خانه‌های مجاور هر کس برابر مجاورهای ضلعی‌اش باشد مسیر خاکستری‌رنگ یک دنباله‌ی شکری از خانه‌ها می‌شود که دنباله‌ی مختصات خانه‌های آن به ترتیب برابر دنباله‌ی زیر است:

$$\langle(2,3),(2,4),(2,5),(3,5),(4,5),(4,4),(5,4),(5,5),(5,6),(5,7),(4,7),(4,8),(4,9),(4,10),(5,10),$$

$$(6,10),(7,10),(7,9),(7,8),(7,7),(7,6),(6,6),(6,7),(6,8),(6,9),(5,9)\rangle$$

ورودی

اعداد یک جدول $2022\times1401$ در یک فایل به نام grid.txt به شما داده شده است. این فایل شامل ۱۴۰۱ خط می‌باشد که در خط $i$ ام آن ۲۰۲۲ عدد قرار دارد که اعداد خانه‌های سطر $i$ ام جدول هستند. در خانه‌های جدول ممکن است اعداد تکراری داشته باشیم؛ ولی در هیچ بلوک $2\times3$ ای (مستطیلی به طول ۲ و عرض ۳) بیشتر ۳ عدد تکراری وجود ندارد! تمام اعداد ورودی نامنفی و کمتر از $10^9$ هستند.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$3$- الف ($33$ نمره) : فرض کنید از هر خانه تنها قادر به رفتن به یکی از دو خانه‌ی راست یا پایین آن هستیم. با این فرض، تعداد مسیرهای شکری جدول ورودی به پیمانه‌ی $\Delta$ چقدر است؟

$3$- ب ($33$ نمره) : فرض کنید از هر خانه تنها قادر به رفتن به خانه‌های با مقدار اکیداً بزرگ‌تر از آن هستیم. با این فرض، تعداد مسیرهای شکری جدول ورودی به پیمانه‌ی $\Delta$ چقدر است؟

$3$- ج ($34$ نمره) : فرض کنید از هر خانه تنها قادر به رفتن به یکی از چهار خانه‌ی مجاور ضلعی آن هستیم. با این فرض، تعداد مسیرهای شکری جدول ورودی به پیمانه‌ی $\Delta$ چقدر است؟