Answer to Question #113047 in C++ for Hasan

Question

From a rectangular sheet of paper tartan (N rows, M columns) have removed some of the cells. How many pieces fall apart the rest of the sheet? Two cells do not break if they have a common side.

Answer 1

#include <iostream>
#include <queue>

using namespace std;

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int n, m;

bool matrix[100][100];

bool check(int y, int x) { return ((0 <= y) && (y < n) && (0 <= x) && (x < m)); }

void fill(int start_y, int start_x) {
    queue<int> queue_y, queue_x;
    queue_y.push(start_y);
    queue_x.push(start_x);
    int y, x;

    while (not queue_y.empty()) {
        y = queue_y.front();
        x = queue_x.front();
        matrix[y][x] = true;
        for (int i = 0; i < 4; i++)
            if (check(y + dy[i], x + dx[i]) and not matrix[y + dy[i]][x + dx[i]]) {
                queue_y.push(y + dy[i]);
                queue_x.push(x + dx[i]);
            }
        queue_y.pop();
        queue_x.pop();
    }
}

int main() {
    cin >> n >> m;
    char ch;
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> ch;
            matrix[i][j] = ch == '.';
        }


    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (not matrix[i][j]) {
                count++;
                fill(i, j);
            }

    cout << count;

    return 0;
}

Input: the first line contains integers N and M, and the next N lines contain M characters each. If the cell was not cut - '#', if cut - '. '

Output: one number - the answer to the problem