Calculating the number of rooms in a 2D house

Question

I stumbled upon this problem on cses.fi (a problem set for the Finnish Olympiad in Informatics. This problem is in finnish so I'll translate it). I'll describe the problem, present the code and think what went wrong.

The problem

You are given a blueprint of a house. The size of the blueprint is \$n * m\$ and each square is either a wall (#) or the floor (.).
Calculate the number of rooms in the house.

Input

On the first row there are two integers: \$n\$ and \$m\$. On the \$n\$ following lines are \$m\$ characters (# or .)

Output

Print the number of rooms in the house.

Limits

\$1 < n, m < 1000\$

Example

Input:

Output:

3

My idea, pseudocode

Step 1:

Loop through the 2D array I've created. Let count = 0.

Step 2:

If the char is '.', search the squares on its left, right, top and bottom. If those squares are '.', add them to the list visit and mark them in the 2D array with count. Go through visit and do step 2 for each element.

Step 3:

When visit is traversed through, one room is ready. Let's increment count and empty visit. Continue step 1.

My c++ code

#include "stdafx.h"
#include <iostream>
#include <vector>

using namespace std;


int main()
{
    int numberofrows;
    int rowlength;
    vector<vector<char>> house;
    cin >> numberofrows >> rowlength;

    for (int i = 0; i < numberofrows; i++) {
        vector<char> add;
        house.push_back(add);
        for (int k = 0; k < rowlength; k++) {
            char mychar;
            cin >> mychar;
            house.back().push_back(mychar);
        }
    }

    int counter = 0;

    for (int row = 0; row < numberofrows; row++) {
        for (int column = 0; column < rowlength; column++) {

            if (house[row][column] != '.') {
                continue;
            }

            vector<vector<int>> visit = {};
            house[row][column] = (char)counter;

            if (row != 0 && house[row - 1][column] == '.') {
                house[row - 1][column] = (char)counter;
                visit.push_back({ row - 1, column });
            }

            if (row != numberofrows - 1 && house[row + 1][column] == '.') {
                house[row + 1][column] = (char)counter;
                visit.push_back({ row + 1, column });
            }

            if (column != 0 && house[row][column - 1] == '.') {
                house[row][column - 1] = (char)counter;
                visit.push_back({ row, column - 1 });
            }

            if (column != rowlength - 1 && house[row][column + 1] == '.') {
                house[row][column + 1] = (char)counter;
                visit.push_back({ row, column + 1 });
            }

            for (int i = 0; i < (int)visit.size(); i++) {


                if (visit[i][0] != numberofrows - 1 && house[visit[i][0] + 1][visit[i][1]] == '.') { //Add the square down from the current square
                    house[visit[i][0] + 1][visit[i][1]] = (char)counter;
                    visit.push_back({ visit[i][0] + 1, visit[i][1] });
                }

                if (visit[i][0] != 0 && house[visit[i][0] - 1][visit[i][1]] == '.') { //Add the square on top of the current square to visit
                    house[visit[i][0] - 1][visit[i][1]] = (char)counter;
                    visit.push_back({ visit[i][0] - 1, visit[i][1] });
                }

                if (visit[i][1] != rowlength - 1 && house[visit[i][0]][visit[i][1] + 1] == '.') { //Add the square on the right of the current square to visit
                    house[visit[i][0]][visit[i][1] + 1] = (char)counter;
                    visit.push_back({ visit[i][0], visit[i][1] + 1 });
                }

                if (visit[i][1] != 0 && house[visit[i][0]][visit[i][1] - 1] == '.') { //Add the square on the left of the current square to visit
                    house[visit[i][0]][visit[i][1] - 1] = (char)counter;
                    visit.push_back({ visit[i][0], visit[i][1] - 1 });
                }

            }
            counter += 1;
        }
    }
    cout << counter;
    return 0;
}

The problems with my code

With the 1000*1000 house, my code sometimes throws a runtime error. I suspect it might be MemoryError as the memory limit is 128 MB. The vector visit might be getting too big. All other improvements are welcome, too! Don't be too harsh as I'm just learning C++.

Answer 1

General remarks

Don't use namespace std;, see for example Why is “using namespace std;” considered bad practice?.

"stdafx.h" is typically used in Visual Studio projects as the name of a header file to be precompiled. To make the code portable, remove the inclusion (your code compiles without it), or wrap it as suggested e.g. here

#ifdef WINDOWS
#include "stdafx.h"
#endif

Don't put everything into main(): With separate function for reading the input and counting the rooms the program becomes more clearly arranged and is better testable.

The final return 0; in main() is not needed.

A problem

While visiting the fields, the '.' character is replaced with the current value of the room counter:

house[row][column] = (char)counter;

As soon as the counter becomes 46 (or whatever the character code for . is on your platform) it is impossible to distinguish between “dot” (for an unvisited field) and the number 46 (for room number 46).

This can indeed cause an infinite loop in your program, e.g. with the input

9 25
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#...#
#########################

The visit vector grows “indefinitely” – until the program aborts with a memory failure.

Fortunately, this can be fixed easily: It is irrelevant for the flood-fill algorithm which room a field belongs to, only if it has been visited or not. So instead of assigning the counter value, assign some character (different from '.' and '#'). Even better, use constants

const char emptyField = '.';
const char visitedField = 'X';

and use them like

if (house[row][column] == emptyField) {
    house[row][column] = visitedField;
    // ...
}

Some simplifications

You are using a “vector of vectors” to store the list of row/column pairs of fields which still have to be visited. A “vector of pairs” would be more appropriate, and requires less memory allocations.

Use an auto variable instead of casting the return value of vector::size():

for (auto i = 0; i < visit.size(); i++) { ...

Even if on Windows (or any other platform with 32-bit integers) int would be large enough for this application, it is generally a good idea to avoid a possible truncation to a smaller integer type.

There are two places where all neighbors of a field are checked: First when an empty field has been found, and again when traversing the visit list. This can be combined, making the main program loop shorter and simpler:

for (int row = 0; row < numberofrows; row++) {
    for (int column = 0; column < rowlength; column++) {

        if (house[row][column] == emptyField) {
            counter += 1;

            vector<pair<int, int>> visit = {{ row, column }};

            for (auto i = 0; i < visit.size(); i++) {
                int r = visit[i].first;
                int c = visit[i].second;
                house[r][c] = visitedField;

                if (r != 0 && house[r - 1][c] == emptyField) {
                    visit.push_back({ r - 1, c });
                }
                if (r != numberofrows - 1 && house[r + 1][c] == emptyField) {
                    visit.push_back({ r + 1, c });
                }
                if (c != 0 && house[r][c - 1] == emptyField) {
                    visit.push_back({ r, c - 1 });
                }
                if (c != rowlength && house[r][c + 1] == emptyField) {
                    visit.push_back({ r, c + 1 });
                }
            }
        }
    }
}

Further suggestions

The visit vector only grows, but never shrinks. Some list might be more memory efficient because you can remove the items that have been handled.

Instead of the flood-fill algorithm, use a “disjoint-set data structure” (also called “union-find data structure”) to find and count connected sets of fields.