DSA sheet / Graph
Counting Rooms
The problem in brief
You get an n by m map (both up to 1000) where each cell is a floor or a wall. A room is a maximal set of floor cells connected through horizontal and vertical steps. Print how many rooms there are.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1192.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Think of the floor cells as nodes and the horizontal/vertical adjacency as edges. What are you counting in that graph?
-
Pick any unvisited floor cell. Which other cells belong to the same room, and how do you enumerate all of them?
-
Start a search (BFS or DFS) from that cell and mark everything it reaches. How many times do you have to start a search?
-
The grid can hold a million cells. What can go wrong with deep recursion, and how would you avoid it?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
“Count the separate blobs” is a connected-components problem, and the standard tool is flood fill: scan the cells; the first time you meet an unvisited floor cell you have found a new room, so add one to the count and then explore the whole room, marking every cell so you never count it again. Each cell is marked once, so the total work is proportional to the number of cells.
The practical risk is depth. A recursive DFS on a snake-shaped room of a million cells recurses a million frames deep, which overflows the stack in most languages. Use an explicit stack or a queue (BFS) instead; both give the same components. The habit: for graph traversals on large inputs, write them iteratively.
Intuition
Pour paint on one floor cell: it spreads to every neighbouring floor cell, and so on until the whole room is painted. Walk the map and each time you find a floor cell that is not painted yet, that is a new room: pour paint again and count.
Approach
- Read the grid; mark walls as visited (or keep a separate visited array).
- For each cell in reading order: if it is an unvisited floor, increment the answer and run a flood fill from it (iterative stack/queue over the four neighbours, marking cells as you push).
- Print the count.
Pitfalls: mark a cell when you push it, not when you pop it, so it is never pushed twice; check bounds before indexing; use iteration, not recursion; read rows as strings.
Complexity
O(n * m) time and memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &row : g) cin >> row;
int rooms = 0;
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<pair<int, int>> stack;
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (g[r][c] != '.') continue;
rooms++;
g[r][c] = '#';
stack.push_back({r, c});
while (!stack.empty()) {
auto [cr, cc] = stack.back();
stack.pop_back();
for (int k = 0; k < 4; k++) {
int nr = cr + dr[k], nc = cc + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] == '.') {
g[nr][nc] = '#';
stack.push_back({nr, nc});
}
}
}
}
}
cout << rooms << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
# Flat bytearray: 1 = unvisited floor, 0 = wall or visited.
floor = bytearray(n * m)
for r in range(n):
row = data[2 + r]
for c in range(m):
if row[c] == '.':
floor[r * m + c] = 1
rooms = 0
for start in range(n * m):
if not floor[start]:
continue
rooms += 1
floor[start] = 0
stack = [start]
while stack:
cell = stack.pop()
r, c = divmod(cell, m)
if r > 0 and floor[cell - m]:
floor[cell - m] = 0
stack.append(cell - m)
if r < n - 1 and floor[cell + m]:
floor[cell + m] = 0
stack.append(cell + m)
if c > 0 and floor[cell - 1]:
floor[cell - 1] = 0
stack.append(cell - 1)
if c < m - 1 and floor[cell + 1]:
floor[cell + 1] = 0
stack.append(cell + 1)
print(rooms)
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
boolean[] floor = new boolean[n * m];
for (int r = 0; r < n; r++) {
String row = in.readLine();
for (int c = 0; c < m; c++) floor[r * m + c] = row.charAt(c) == '.';
}
int rooms = 0;
int[] stack = new int[n * m];
for (int start = 0; start < n * m; start++) {
if (!floor[start]) continue;
rooms++;
floor[start] = false;
int top = 0;
stack[top++] = start;
while (top > 0) {
int cell = stack[--top];
int r = cell / m, c = cell % m;
if (r > 0 && floor[cell - m]) { floor[cell - m] = false; stack[top++] = cell - m; }
if (r < n - 1 && floor[cell + m]) { floor[cell + m] = false; stack[top++] = cell + m; }
if (c > 0 && floor[cell - 1]) { floor[cell - 1] = false; stack[top++] = cell - 1; }
if (c < m - 1 && floor[cell + 1]) { floor[cell + 1] = false; stack[top++] = cell + 1; }
}
}
System.out.println(rooms);
}
}const lines = require('fs').readFileSync(0, 'utf8').split('\n');
const [n, m] = lines[0].trim().split(/\s+/).map(Number);
const floor = new Uint8Array(n * m);
for (let r = 0; r < n; r++) {
const row = lines[1 + r];
for (let c = 0; c < m; c++) floor[r * m + c] = row[c] === '.' ? 1 : 0;
}
let rooms = 0;
const stack = new Int32Array(n * m);
for (let start = 0; start < n * m; start++) {
if (!floor[start]) continue;
rooms++;
floor[start] = 0;
let top = 0;
stack[top++] = start;
while (top > 0) {
const cell = stack[--top];
const r = Math.floor(cell / m);
const c = cell - r * m;
if (r > 0 && floor[cell - m]) { floor[cell - m] = 0; stack[top++] = cell - m; }
if (r < n - 1 && floor[cell + m]) { floor[cell + m] = 0; stack[top++] = cell + m; }
if (c > 0 && floor[cell - 1]) { floor[cell - 1] = 0; stack[top++] = cell - 1; }
if (c < m - 1 && floor[cell + 1]) { floor[cell + 1] = 0; stack[top++] = cell + 1; }
}
}
console.log(rooms);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).