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++.
house[row][column]
which is achar
. – And how would you distinguish if'.'
means "dot" or "counter is 46" ? \$\endgroup\$