[BOJ]10026-赤色薬水

https://www.acmicpc.net/problem/10026
質問する
赤緑の薬水はほとんど赤緑の違いを感じない.そのため、赤緑色の弱い人が見る絵とは違います.
サイズN×Nインチメッシュの各格子には、R(赤)、G(緑)、B(青)を塗った図があります.図はいくつかの領域に分けられ、領域は同じ色で構成されています.また、同じ色が上下左右に隣接している場合、2文字は同じ領域に属する.(色の違いがほとんど感じられない場合は同じ色とも呼ばれます)
たとえば、図が次のように表示されている場合.

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

赤い薬ではない人から見れば、エリアの総数は4つです.(赤2、青1、緑1)しかし赤の人は3つのエリアを見ることができます.(赤-緑2、青1)
画像が入力されると、赤と非赤の人が見る領域数を求めるプログラムを作成します.
入力
1行目はNです.(1 ≤ N ≤ 100)
2行目からN行目に1枚の図が与えられます.
しゅつりょく
赤緑色薬ではない人が見た領域数と赤緑色薬の人が見た領域数を空白に分けて出力します.
サンプルI/O
入力

例1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

例出力1

4 3

Solution

#include <iostream>
#include <queue>
#define MAX 100
using namespace std;

int N;
char MATRIX[MAX][MAX];
bool visit[MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void phase2(){
    for(int i = 0; i < MAX; i++){
        for(int j = 0; j < MAX; j++) visit[i][j] = false;
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(MATRIX[i][j] == 'G') MATRIX[i][j] = 'R';
        }
    }
}

void BFS(int X, int Y){
    queue<pair<int, int>> Q;
    Q.push({X, Y});
    visit[X][Y]= true;
    char currentColor = MATRIX[X][Y];
    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < N && !visit[nx][ny] && MATRIX[nx][ny] == currentColor){
                visit[nx][ny] = true;
                Q.push({nx, ny});
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) cin >> MATRIX[i][j];
    }
    int result1 = 0, result2 = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(!visit[i][j]){
                BFS(i, j);
                result1 += 1;
            }
        }
    }
    phase2();
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(!visit[i][j]){
                BFS(i, j);;
                result2 += 1;
            }
        }
    }
    cout << result1 << " " << result2 << '\n';
}

簡単です.BFSを2回やって、2回目のBFSをやる前に、Gの代わりにRを使えばいいです.

  for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) cin >> MATRIX[i][j];
    }
    int result1 = 0, result2 = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(!visit[i][j]){
                BFS(i, j);
                result1 += 1;
            }
        }
    }

すべてのデータを入力してBFSを実行すると、いずれにしても4方向の領域が見つかり、それぞれの場合カウントされます.

void BFS(int X, int Y){
    queue<pair<int, int>> Q;
    Q.push({X, Y});
    visit[X][Y]= true;
    char currentColor = MATRIX[X][Y];
    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < N && !visit[nx][ny] && MATRIX[nx][ny] == currentColor){
                visit[nx][ny] = true;
                Q.push({nx, ny});
            }
        }
    }
}

その後BFSを行いますが、始点の基準色をナビゲートします.char currentColorに注目してください.3色に対して異なるBFSコードを記述する必要はありません.(最初はもう少しでそうだったけど)

void phase2(){
    for(int i = 0; i < MAX; i++){
        for(int j = 0; j < MAX; j++) visit[i][j] = false;
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(MATRIX[i][j] == 'G') MATRIX[i][j] = 'R';
        }
    }
}

そしてvisit配列を初期化し,先ほど述べたようにMATRIXのすべてのGをRに変換し,同様に探索を繰り返す.
BFSの運用を知っていれば、難しくはありません.