【USACO】The Castle

flood fill 方法，将整个地图按照房间进行着色，0意思是还未访问的房间。

在着色同时计算最大的房间，而颜色种类就是房间的数量。

最后枚举墙，如果推到墙后，对应的两个格子分属不同的房间，则将房间的size相加，并更新推倒墙后得到的最大的房间的size。

/*
ID :
LANG: C++11
TASK: castle
 */

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M;
int size[2600] = {};
int color = 0;
int map[55][55] = {};
int wall[55][55];
queue<pair<int, int>> flood;
int direction[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};

int maxRoomSize = 0;
int maxRoomSizeRemove = 0;
pair<pair<int, int>, char> wallRemoved;

int main()
{
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    cin >> M >> N;
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < M; j ++){
            cin >> wall[i][j];
        }
    }
    typedef pair<int, int> cord;

    //color the map, one room, one color
    //calculate the maxRoomSize and how many rooms are here in the house
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < M; j ++){
            if (map[i][j] == 0){
                flood.push(cord(i, j));
                color ++;
                map[i][j] = color;
                while (!flood.empty()){
                    cord room = flood.front();
                    flood.pop();
                    size[color] ++;
                    for (int k = 0; k < 4; k ++){
                        if (!((wall[room.first][room.second] >> k) & 1) && map[room.first + direction[k][0]][room.second + direction[k][1]] == 0){
                            map[room.first + direction[k][0]][room.second + direction[k][1]] = color;
                            flood.push(cord(room.first + direction[k][0], room.second + direction[k][1]));
                        }
                    }
                }
                if (size[color] > maxRoomSize) {
                    maxRoomSize = size[color];
                }
            }
        }
    }

    //enumerate the walls and calculate the biggest room after remove the wall.

    for (int j = 0; j < M; j ++){
        for (int i = N - 1; i >= 0; i --){
            for (int k = 1; k <= 2; k ++){
                if (((wall[i][j] >> k) & 1) && (i + direction[k][0] >= 0) && (j + direction[k][1] < M)){
                    if (map[i][j] != map[i + direction[k][0]][j + direction[k][1]]){
                        int tSize = size[map[i][j]] + size[map[i + direction[k][0]][j + direction[k][1]]];
                        if (tSize > maxRoomSizeRemove){
                            maxRoomSizeRemove = tSize;
                            wallRemoved.first.first = i;
                            wallRemoved.first.second = j;
                            wallRemoved.second = k == 1 ? 'N' : 'E';
                        }
                    }
                }
            }
        }
    }
    cout << color << endl << maxRoomSize << endl;
    cout << maxRoomSizeRemove << endl;
    cout << wallRemoved.first.first + 1 << ' ' << wallRemoved.first.second + 1 << ' ' << wallRemoved.second << endl;

}