counting-rooms

Counting Rooms

CSES easy

أُعطيت خريطة لمبنى، ومهمتك حساب عدد الغرف فيه. حجم الخريطة هو n × m مربعات، وكل مربع إما أرضية أو جدار. يمكنك المشي يساراً ويميناً وأعلى وأسفل عبر مربعات الأرضية.

المدخل:

السطر الأول: عددان صحيحان n و m — الارتفاع والعرض.
ثم n أسطر: كل سطر يحتوي m حرفاً:
- . أرضية
- # جدار

المخرجات:

اطبع عدداً صحيحاً واحداً: عدد الغرف.

القيود:

1 ≤ n, m ≤ 1000

مثال:

المدخل:

5 8
########
#..#...#
####.#.#
#..#...#
########

المخرجات:

Solution

“الغرفة” هي بالضبط مكوّن متصل من خلايا الأرضية . باستخدام حركات بأربعة اتجاهات.

إذن تصبح المهمة:

احسب كم مكوّناً متصلاً من . موجوداً في الشبكة.

نمسح الشبكة. كلما وجدنا خلية أرضية غير مُزارة، نبدأ منها BFS/DFS ونعلّم جميع خلايا الأرضية القابلة للوصول على أنها مُزارة. كل بداية كهذه تمثل غرفة واحدة.

فكرة الرسم البياني

اعتبر كل خلية أرضية عقدة. وأضف أحرفاً بين خلايا الأرضية المتجاورة (أعلى/أسفل/يسار/يمين). حينها كل غرفة هي مكوّن متصل واحد في هذا الرسم البياني.

الجواب النهائي

المتغير rooms بعد المسح يساوي عدد المكوّنات المتصلة لخلايا .، وهذا بالضبط هو عدد الغرف.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;

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

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

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

    vector<vector<char>> vis(n, vector<char>(m, 0));
    int rooms = 0;

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '.' || vis[i][j]) continue;

            rooms++;
            queue<pair<int,int>> q;
            q.push({i, j});
            vis[i][j] = 1;

            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();

                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (grid[nr][nc] != '.' || vis[nr][nc]) continue;
                    vis[nr][nc] = 1;
                    q.push({nr, nc});
                }
            }
        }
    }

    cout << rooms << "\n";
    return 0;
}