[BOJ / C++] 6186번 : Best Grass

문제

Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 <= R <= 100) rows and C (1 <= C <= 100) columns. She wishes to count the number of grass clumps in the pasture.

Each grass clump is shown on a map as either a single '#' symbol or perhaps two '#' symbols side-by-side (but not on a diagonal). No two symbols representing two different clumps are adjacent. Given a map of the pasture, tell Bessie how many grass clumps there are.

By way of example, consider this pasture map where R=5 and C=6:

.#....
..#...
..#..#
...##.
.#....

This pasture has a total of 5 clumps: one on the first row, one that spans the second and third row in column 2, one by itself on the third row, one that spans columns 4 and 5 in row 4, and one more in row 5.

입력

• Line 1: Two space-separated integers: R and C
• Lines 2..R+1: Line i+1 describes row i of the field with C characters, each of which is a '#' or a '.'

출력

• Line 1: A single integer that is the number of grass clumps Bessie can munch 

Solved.ac 레벨

실버 V

풀이

#include <bits/stdc++.h>
#define MAX 101

using namespace std;

int r, c, result;
char MAP[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int> > q;

void BFS(pair<int, int> p) {
    visited[p.first][p.second] = true;
    q.push(p);

    while(!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nX = curX + dx[i];
            int nY = curY + dy[i];

            if(nX >= 0 && nY >= 0 && nX < r && nY < c) {
                if(!visited[nX][nY] && MAP[nX][nY] == '#') {
                    visited[nX][nY] = true;
                    q.push(make_pair(nX, nY));
                }
            }
        }

    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> MAP[i][j];
        }
    }

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(MAP[i][j] == '#' && !visited[i][j]) {
                result++;
                BFS(make_pair(i, j));
            }
        }
    }

    cout << result << "\n";

    return 0;
}

 

 

6186번: Best Grass