城堡问题-双重解法

//输入数据
//格式：[Y轴][X轴][四个方向]
//其中，四个方向分别为：
//  0 - left
//  1 - up
//  2 - right
//  3 - down
bool input[50][50][4];
//标记某个点是否被搜索过
bool vis[50][50];
int height, width;

int solve(int _x, int _y) {
    static pair<int, int> all[] = {
            {-1, 0},    {0, -1},
            {1, 0},    {0, 1}
    };
    int result = 0;
    queue<pair<int, int>> queue;
    queue.emplace(_x, _y);
    do {
        auto node = queue.front();    queue.pop();
        int x = node.first, y = node.second;
        if (vis[y][x]) continue;
        vis[y][x] = true;
        ++result;
        for (int i = 0; i != 4; ++i) {
            int nx = x + all[i].first;
            int ny = y + all[i].second;
            //检查点是否在地图内，防止越界
            if (ny == -1 || nx == -1 || ny == height || nx == width) continue;
            //检查两个房间是否连接，稳妥起见两个房间都检查
            //(i + 2) % 4 就是取反方向
            if (input[y][x][i] && input[ny][nx][(i + 2) % 4]) queue.emplace(nx, ny);
        }
    } while (!queue.empty());
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    int value;
    cin >> height >> width;
    for (int y = 0; y != height; ++y) {
        for (int x = 0; x != width; ++x) {
            cin >> value;
            for (int i = 0; i != 4; ++i) {
                input[y][x][i] = !((value >> i) & 1);
            }
        }
    }
    int amount = 0;
    int maxValue = 0;
    for (int y = 0; y != height; ++y) {
        for (int x = 0; x != width; ++x) {
            if (!vis[y][x]) {
                ++amount;
                maxValue = max(maxValue, solve(x, y));
            }
        }
    }
    printf("%d\n%d", amount, maxValue);
    return 0;
}

struct {
    // 0 - left
    // 1 - up
    // 2 - right
    // 3 - down
    bool link[4]{};
    //并查集下标
    int index = 0;
} input[50][50];

int check[50*50];
int height, width;

int find(int index) {
    if (index == check[index]) return index;
    return check[index] = find(check[index]);
}

//尝试连接
//参数：
//  x, y - 坐标
//  hor  - 是否是横向连接
void tryLink(int x, int y, bool hor) {
    int direct = hor ? 0 :   1;     //邻接方向
    int nx = hor ? x - 1 :   x;     //相邻点的横坐标
    int ny = hor ?   y   : y - 1;   //相邻点的纵坐标
    //边界检查
    if (nx == -1 || ny == -1 || nx == width || ny == height) return;
    //连接检查
    if (input[y][x].link[direct] && input[ny][nx].link[direct + 2]) {
        //合并
        check[find(input[y][x].index)] = find(input[ny][nx].index);
    }
}

void solve(int index) {
    for (int y = 0; y != height; ++y) {
        for (int x = 0; x != width; ++x) {
            tryLink(x, y, true);
            tryLink(x, y, false);
        }
    }
    map<int, int> record;
    int ans = 0;
    for (int i = 0; i != index; ++i) ans = max(ans, ++record[find(i)]);
    printf("%lu\n%d", record.size(), ans);
}

int main() {
    ios::sync_with_stdio(false);
    int value, index = 0;
    cin >> height >> width;
    for (int y = 0; y != height; ++y) {
        for (int x = 0; x != width; ++x) {
            cin >> value;
            check[index] = index;
            input[y][x].index = index++;
            for (int i = 0; i != 4; ++i) {
                input[y][x].link[i] = !((value >> i) & 1);
            }
        }
    }
    solve(index);
    return 0;
}