التعرف على الأنماط

التعرف على الأنماط

الأولمبياد الوطني للبرمجة 2026 - المسابقة الثالثة

الزمن المحدد: 1 ثانية
الذاكرة المحددة: 256 ميجابايت

لقد اشتريت للتو صحراء! الصحراء مقسّمة إلى \(n\) صفًا و \(m\) عمودًا. في الخلية الواقعة عند الصف \(i\) والعمود \(j\)، يوجد جمل من النوع \(A_{i,j}\). يوجد \(k\) نوعًا من الجمال إجمالًا، لذا فإن كل \(A_{i,j}\) هو عدد صحيح بين \(1\) و \(k\).

أنت مهتم بالمناطق الخاصة في الصحراء. تُعدّ المنطقة خاصة إذا تحقق ما يلي: - أن تكون مستطيلة الشكل، - أن تكون جميع الجمال داخلها من النوع نفسه، - وأن يظهر هذا النوع داخل ذلك المستطيل فقط ولا يظهر في أي مكان آخر.

مهمتك هي تحديد عدد المناطق الخاصة التي تحتويها الصحراء.

المدخلات

يحتوي السطر الأول من الإدخال على ثلاثة أعداد صحيحة \(n\) و\(m\) و\(k\)، حيث \((1 \leq n, m \leq 2000), (1 \leq k \leq 10^6)\)، وهي عدد صفوف الصحراء وعدد أعمدتها وعدد أنواع الجمال على الترتيب.

يحتوي كل سطر من الأسطر الـ \(n\) التالية على \(m\) عددًا صحيحًا مفصولة بمسافات. يمثل العدد الـ \(j\) في السطر الـ \(i\) القيمة \(A_{i,j}\)، وهي نوع الجمل في الصف \(i\) والعمود \(j\).

المخرجات

اطبع عددًا صحيحًا واحدًا، وهو عدد المناطق الخاصة في الصحراء.

التقييم

في هذه المسألة، يتم التقييم وفقًا للمجموعات الفرعية الموضحة أدناه. درجة الإرسال هي مجموع نقاط جميع المجموعات الفرعية المُجتازة في إرسال واحد، بينما درجة المسألة هي أعلى درجة إرسال تحققها عبر جميع محاولاتك.

المجموعة الفرعية	القيود الإضافية	النقاط
\(1\)	\(n, m \le 20\)	\(14\)
\(2\)	\(n, m \le 100, k \le 100\)	\(16\)
\(3\)	\(n, m \le 100\)	\(17\)
\(4\)	\(k = 2\)	\(22\)
\(5\)	لا توجد قيود إضافية	\(31\)

أمثلة

المدخلات

3 4 3
1 1 2 2
1 1 2 3
3 3 3 3

المخرجات

1

المدخلات

4 5 4
1 1 2 2 2
1 1 2 2 2
3 3 3 4 4
3 3 3 4 4

المخرجات

4

ملاحظة

الإدخال السريع: لاجتياز القيود الكاملة، قد تحتاج إلى استخدام إدخال/إخراج سريع. في C++، أضف الأسطر التالية في بداية دالة main:

ios::sync_with_stdio(false);
cin.tie(nullptr);

شرح الأمثلة:

في المثال الأول، يُشكّل النوع \(1\) مستطيلًا تامًا بأبعاد \(2 \times 2\) ولا يظهر في أي مكان آخر، لذا فهو صالح. النوع \(2\) له صندوق محيط بأبعاد \(2 \times 2\)، لكن إحدى الخلايا داخله ليست من النوع \(2\)، لذا فهو غير صالح. النوع \(3\) يظهر في عدة صفوف وصندوقه المحيط يحتوي على خلايا ليست من النوع \(3\)، لذا فهو غير صالح. وبالتالي، توجد منطقة خاصة واحدة بالضبط.

في المثال الثاني، كل نوع (\(1\)، \(2\)، \(3\)، \(4\)) يُشكّل مستطيلًا واحدًا كاملًا ولا يظهر في أي مكان آخر. جميعها تحقق الشروط، لذا فالإجابة هي \(4\).

الحل

أوجد لكل نوع من الإبل أصغر وأكبر صف وعمود. تحدد القيم الأربع المستطيل الوحيد الذي قد يحتوي كل ظهور لذلك النوع. احسب عدد مرات ظهوره أيضًا؛ يملأ النوع مستطيله المحيط بالضبط عندما يساوي العدد \((\text{أكبر صف}-\text{أصغر صف}+1)(\text{أكبر عمود}-\text{أصغر عمود}+1)\). عندها تشكل كل خلايا المستطيل منطقة خاصة واحدة. التعقيد \(O(NM+K)\) زمنيًا و\(O(K)\) للذاكرة.

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

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

        int n, m, k;
        cin >> n >> m >> k;

        vector<int> minRow(k + 1, n), maxRow(k + 1, -1);
        vector<int> minCol(k + 1, m), maxCol(k + 1, -1);
        vector<int> count(k + 1, 0);

        for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {
                        int type;
                        cin >> type;
                        minRow[type] = min(minRow[type], row);
                        maxRow[type] = max(maxRow[type], row);
                        minCol[type] = min(minCol[type], col);
                        maxCol[type] = max(maxCol[type], col);
                        count[type]++;
                }
        }

        int answer = 0;

        for (int type = 1; type <= k; type++) {
                if (count[type] == 0) continue;

                long long area = 1LL * (maxRow[type] - minRow[type] + 1)
                                                            * (maxCol[type] - minCol[type] + 1);
                if (area == count[type]) {
                        answer++;
                }
        }

        cout << answer << '\n';
}