counting-rooms

Counting Rooms

CSES easy

You are given a map of a building, and your task is to count the number of its rooms. The size of the map is n × m squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.

Input:

First line: integers n and m — height and width.
Next n lines: each has m characters:
- . floor
- # wall

Output:

Print one integer: the number of rooms.

Constraints:

1 ≤ n, m ≤ 1000

Example:

Input:

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

Output:

Solution

A “room” is exactly a connected component of floor cells (.) using 4-direction moves.

So the task becomes:

Count how many connected components of . exist in the grid.

We scan the grid. Whenever we find an unvisited floor cell, we start a BFS/DFS from it and mark all reachable floor cells as visited. Each such start corresponds to one room.

Graph idea

Think of each floor cell as a node. Add edges between adjacent floor cells (up/down/left/right). Then each room is one connected component in this graph.

Final answer

The variable rooms after scanning is the number of connected components of . cells, which is exactly the number of 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;
}