Grid Paths I

Grid Paths I
CSES easy

اعتبر شبكة بحجم \(n \times n\)، قد تحتوي بعض مربعاتها على فخاخ. لا يُسمح لك بالتحرك إلى مربع يحتوي على فخ.

مهمتك هي حساب عدد المسارات من المربع العلوي الأيسر إلى المربع السفلي الأيمن. يمكنك التحرك فقط إلى اليمين أو إلى الأسفل.

الإدخال:

  • السطر الأول: عدد صحيح \(n\) — حجم الشبكة.

  • السطور \(n\) التالية: يحتوي كل سطر على \(n\) محارف:

    • . تمثّل خلية فارغة
    • * تمثّل فخًا

المخرجات:

  • اطبع عدد المسارات الصحيحة، بتطبيق باقي القسمة على \(10^9 + 7\).

القيود:

  • \(1 \le n \le 1000\)

مثال:

الإدخال:

4
....
.*..
...*
*...

المخرجات:

3

Solution

نريد عدّ المسارات من \((0,0)\) إلى \((n-1,n-1)\) مع السماح بالحركة إلى اليمين أو الأسفل فقط، ومنع الدخول إلى أي خلية تحمل *.

هذه مسألة برمجة ديناميكية قياسية على الشبكات.

فكرة الـ DP (حساب متسلسل)

لنعرّف dp[i][j] على أنه عدد الطرق للوصول إلى الخلية \((i,j)\) بدايةً من \((0,0)\).

  • إذا كانت الخلية \((i,j)\) فخًا: dp[i][j] = 0.

  • وإلا يمكننا الوصول إليها من:

    • الأعلى: \((i-1,j)\) عبر نزول خطوة،
    • اليسار: \((i,j-1)\) عبر حركة إلى اليمين.

إذًا للخلية الفارغة:

\[ dp[i][j] = \begin{cases} 0, & \text{if } g_{i,j} = \ast,\\[4pt] 1, & (i,j) = (0,0) \text{ and } g_{0,0} \neq \ast,\\[4pt] \bigl(dp[i-1][j] + dp[i][j-1]\bigr) \bmod M, & \text{otherwise}. \end{cases} \]

حيث \(M = 10^9 + 7\).

نملأ الجدول بالتتابع باستخدام حلقتين متداخلتين:

  • i من 0 إلى n-1،
  • j من 0 إلى n-1.

الجواب هو dp[n-1][n-1].

برهان SRTBOT مختصر

S — State (الحالة)

dp[i][j] = عدد المسارات الصحيحة من الخلية الابتدائية \((0,0)\) إلى الخلية \((i,j)\)، مع الالتزام بأن:

  • الحركة فقط إلى اليمين أو الأسفل،
  • لا ندخل أي خلية فخ *.

ما نريده في النهاية هو حالة الهدف dp[n-1][n-1].

R — Recurrence (العلاقة العودية)

للخلية غير الفخ \((i,j)\) (أي grid[i][j] == '.'):

  • أي مسار يصل إلى \((i,j)\) لا يمكن أن يأتي إلا من:

    • الأعلى \((i-1,j)\) أو
    • اليسار \((i,j-1)\)،

لأن الحركات الوحيدة المسموحة هي إلى اليمين أو الأسفل، ولا توجد طرق أخرى للدخول.

لذا:

\[ dp[i][j] = dp[i-1][j] + dp[i][j-1] \pmod M, \]

مع اعتبار أي مؤشر خارج الحدود يساهم بـ 0.

إذا كانت grid[i][j] == '*':

\[ dp[i][j] = 0, \]

لأننا لا يمكن أن نقف على خلية فخ.

T — Transition (الانتقال في الكود)

في الكود، لكل خلية:

if (grid[i][j] == '*') dp[i][j] = 0;
else if (i == 0 && j == 0) dp[i][j] = 1;
else {
    long long from_up   = (i > 0 ? dp[i-1][j] : 0);
    long long from_left = (j > 0 ? dp[i][j-1] : 0);
    dp[i][j] = (from_up + from_left) % MOD;
}

وهذا يطبّق العلاقة العودية مباشرة.

B — Base cases (الحالات الابتدائية)

  • الخلية الابتدائية \((0,0)\):

    • إذا كانت فخًا → لا يوجد أي مسار → dp[0][0] = 0 (مغطاة بحالة الفخ).

    • إذا كانت فارغة → يوجد مسار واحد فقط يبدأ منها:

      dp[0][0] = 1.

  • الصف الأول (i = 0, j > 0):

    • يمكن الوصول إليه فقط من اليسار، ولا يوجد صف أعلى.

    • العلاقة مع dp[i-1][j] = 0 تعطي تلقائيًا:

      • dp[0][j] = dp[0][j-1] إذا لم تكن الخلية فخًا، وإلا 0.

  • العمود الأول (j = 0, i > 0):

    • يمكن الوصول إليه فقط من الأعلى؛ والحدود تُدار بنفس الطريقة.

كل هذه الحالات تُغطّى تلقائيًا عبر القواعد العامة مع فحص حدود المصفوفة.

O — Order of computation (ترتيب الحساب)

نكرّر على (i,j) بترتيب الصفوف:

  • الحلقة الخارجية: i = 0..n-1
  • الحلقة الداخلية: j = 0..n-1

عند حساب dp[i][j] نستخدم فقط:

  • dp[i-1][j] (الصف السابق)،
  • dp[i][j-1] (العمود السابق في نفس الصف)،

وكلتاهما تم حسابهما سابقًا لأن:

  • i-1 < i،
  • j-1 < j.

إذًا الترتيب صحيح والـ DP معرّف جيدًا.

T — Time and Space Complexity (التعقيد)

  • عدد الخلايا \(n^2\).
  • لكل خلية، نقوم بعمل ثابت \(O(1)\).

إذًا:

  • الزمن: \(O(n^2)\) (حتى \(10^6\) عملية تقريبًا، وهذا مناسب).
  • الذاكرة: \(O(n^2)\) لجدول dp.

النتيجة النهائية

القيمة dp[n-1][n-1] هي بالضبط عدد المسارات الصحيحة من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى، بتطبيق باقي القسمة على \(10^9+7\).

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // dp[i][j] = number of ways to reach (i, j)
    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '*') {
                dp[i][j] = 0; // cannot use traps
                continue;
            }

            if (i == 0 && j == 0) {
                dp[i][j] = 1; // starting cell (if not trap)
            } else {
                long long from_up   = (i > 0 ? dp[i - 1][j] : 0);
                long long from_left = (j > 0 ? dp[i][j - 1] : 0);
                dp[i][j] = (from_up + from_left) % MOD;
            }
        }
    }

    cout << dp[n - 1] [n - 1] << "\n";
    return 0;
}
Cautionملاحظات حول المودولو والحدود
  • نتأكد دائمًا من أخذ النتيجة بتطبيق باقي القسمة على \(10^9 + 7\).
  • نتجنب الخروج عن حدود المصفوفة باستخدام فحص الشرطين i > 0 و j > 0 قبل الوصول إلى dp[i-1][j] أو dp[i][j-1].
  • إذا كانت خلية الهدف فخًا، فسيكون الناتج تلقائيًا 0 لأن dp[n-1][n-1] سيُضبط إلى صفر.