城堡问题

思路

这道题目乍一看感觉挺复杂的，其实它的本质还是一个Flood Fill算法，代码还是那些，大概只有一行不一样。

首先来看这个模型，一个房间其实就是一个连通块，题目让求所有的连通块的数量还有最大的面积，那无非就是使用BFS 或者DFS遍历一遍图。问题的关键在于这个输入好复杂啊，有点不明所以，但是经过仔细分析，就可以发现这是一个二进制形式的表示方法，对于某个方向，只需要看特定的第几位是零还是1就行了。

为了方便，这里顶的的方向向量与之前的不太一致，主要是为了使得方向i和二进制第i位对应。然后判断从当前块能不能走到相邻的块只需要一句话就可以了。十分巧妙

if(g[a][b] >> i & 1) continue;//不能到达

代码

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 55;

int n, m;
int g[N][N];
bool st[N][N];
//返回最大房间面积
int bfs(int x, int y)
{
    int area = 0;
    queue<PII> q;    
    q.push({x, y});
    st[i][j] = true;

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

    while(q.size())
    {
        auto t = q.front();q.pop();
        area++;

        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];

            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[i][j]) continue;

            if(g[a][b] >> i & 1) continue;//关键

            q.push({a, b});
            st[a][b] = true;
        }
    }
    return area;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> g[i][j];
        }
    }

    int cnt = 0, area = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(!st[i][j])
            {
                cnt++;
                area = max(area, bfs(i,j));
            }
        }
    }

    cout << cnt << endl << area << endl;

    return 0;
}