백준 2234 성곽 C++

#include<bits/stdc++.h>

#define MAX 50

using namespace std;

 

int N, M;

int MAP[MAX][MAX];

bool chk[MAX][MAX];

int dx[] = { 0, -1, 0, 1 };

int dy[] = { -1, 0, 1, 0 };

 

int BFS(int a, int b){

    int roomSize = 0;

    queue<pair<int, int>> Q;

    Q.emplace(a, b);

    chk[a][b] = true;

    roomSize++;

    while (!Q.empty()){

        int x = Q.front().first;

        int y = Q.front().second;

        Q.pop();

        int w = 1;

        for (int i = 0; i < 4; i++){

            if ((MAP[x][y] & w) != w){

                int nx = x + dx[i];

                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < M){

                    if (!chk[nx][ny]){

                        roomSize++;

                        chk[nx][ny] = true;

                        Q.emplace(nx, ny);

                    }

                }

            }

            w = w * 2;

        }

    }

    return roomSize;

}

 

int main(void){

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cin >> M >> N;

    for (int i = 0; i < N; i++){

        for (int j = 0; j < M; j++)

            cin >> MAP[i][j];

    }

    int Room_Cnt = 0;

    int biggest = 0;

 

    for (int i = 0; i < N; i++){

        for (int j = 0; j < M; j++){

            if (chk[i][j] == false){

                biggest = max(biggest, BFS(i,j));

                Room_Cnt++;

            }

        }

    }

 

    cout << Room_Cnt << '\n';

    cout << biggest << '\n';

 

    for (int i = 0; i < N; i++){

        for (int j = 0; j < M; j++){

            for (int w = 1; w <= 8; w *= 2){

                if ((MAP[i][j] & w) == w){

                    memset(chk, false, sizeof(chk));

                    MAP[i][j] = MAP[i][j] - w;

                    biggest = max(biggest, BFS(i, j));

                    MAP[i][j] = MAP[i][j] + w;

                }

            }

        }

    }

    cout << biggest;

    return 0;

}