信息学奥赛一本通 1250：The Castle | OpenJudge NOI 2.5 166:The Castle

ybt 1250：The Castle
OpenJudge NOI 2.5 166:The Castle

该题难点在于如何表示一个方块在各个方向上是否有墙。
题目说用一个整数表示一个方格哪面有墙：1西，2北，4东，8南，如果有这堵墙，那么就有对应的数字参与加和。设这个整数为 m m m。
看给出的表示方向的四个数字，分别为 2 0 , 2 1 , 2 2 , 2 3 2^0, 2^1, 2^2, 2^3 20,21,22,23。
设数字 d i d_i di​（i为0表示西，i为1表示北，i为2表示东，i为3表示南）， d i d_i di​表示其对应的方向上是否有墙，如果有墙 d i = 1 d_i=1 di​=1，无墙 d i = 0 d_i=0 di​=0
那么这个表示墙情况的整数为 m = d 3 ∗ 2 3 + d 2 ∗ 2 2 + d 1 ∗ 2 1 + d 0 ∗ 2 0 m=d_3*2^3+d_2*2^2+d_1*2^1+d_0*2^0 m=d3​∗23+d2​∗22+d1​∗21+d0​∗20，这正是数字m在二进制下的按位权展开式，或者说整数 m m m的二进制表示为 d 3 d 2 d 1 d 0 d_3d_2d_1d_0 d3​d2​d1​d0​。
只需要对数字m做二进制下的数字拆分，即可得知该位置周围四个方向墙的情况。
例如像如下形式

for(int a = m; a > 0; a /= 2)
	cout << a%2 << ' ';

这段代码可以按顺序分别输出 d 0 , d 1 , d 2 , d 3 d_0,d_1,d_2,d_3 d0​,d1​,d2​,d3​，也就是该位置西北东南四个方向的墙的情况。

接下来使用连通块问题的通用解法即可。
遍历整个地图，尝试从每个位置开始进行搜索，如果成功进行一次搜索，那么存在一个连通块，也就是房间。每搜索到一个位置，根据该位置的 m m m值来获得该位置周围墙的信息，如果该某一方向上没有墙，而且该方向上的下一个位置在地图内且没访问过，那么就从下一个位置开始进行搜索。搜索时，要同时统计该连通块中格子的个数。在搜索结束后，更新连通块格子的最大值。
最后输出连通块个数，即连通块中格子数的最大值。

该问题可以用深搜或广搜方法来解。
注意：方向数组中设置的四个方向的顺序必须为“西北东南”，也就是“左上右下”，这与从数字m中获取到各个方向是否有墙的顺序是一致的。

#include 
using namespace std;
#define N 55
int m, n, num, mx, sn;//num：房间数 sn：房间中格子数 mx：房间最大格子数 
int mp[N][N], dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};//0西1北2东3南 
bool vis[N][N];//vis[i][j]:第(i,j)位置是否已访问 
void dfs(int sx, int sy)//从(sx,sy)开始进行深搜
{
    int a = mp[sx][sy];//mp[sx][sy]为题解中的m值 
    for(int i = 0; i < 4; ++i)
    {
        int x = sx + dir[i][0], y = sy + dir[i][1];
        if(x >= 1 && x <= m && y >= 1 && y <= n && a % 2 == 0 && vis[x][y] == false)//a%2 == 0：dir[i]表示的方向没有墙 
        {
            vis[x][y] = true;
            sn++;
            dfs(x, y);
        }
        a /= 2;
    }
}
int main()
{   
    cin >> m >> n;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> mp[i][j];
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(vis[i][j] == false)
            {
                sn = 1;
                vis[i][j] = true;
                dfs(i, j);
                mx = max(mx, sn);//更新房间最大格子数 
                num++;//每成功进行一次广搜，房间数（连通块数）加1 
            }
        }
    cout << num << endl << mx;
    return 0;
}

#include 
using namespace std;
#define N 55
struct Node
{
    int x, y;
    Node(){}
    Node(int a, int b):x(a),y(b){}
};
int m, n, num, mx;//num：房间数 mx：房间最大格子数 
int mp[N][N], dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};//0西1北2东3南 
bool vis[N][N];//vis[i][j]:第(i,j)位置是否已访问 
int bfs(int sx, int sy)//从(sx,sy)开始进行广搜，返回该房间（连通块）的格子数 
{
    int sn = 1;//该房间的格子数 
    queue que;
    vis[sx][sy] = true;
    que.push(Node(sx, sy));
    while(que.empty() == false)
    {
        Node u = que.front();
        que.pop();
        int a = mp[u.x][u.y];//mp[u.x][u.y]为题解中的m值 
        for(int i = 0; i < 4; ++i)
        {
            int x = u.x + dir[i][0], y = u.y + dir[i][1];
            if(x >= 1 && x <= m && y >= 1 && y <= n && a % 2 == 0 && vis[x][y] == false)//a%2 == 0：dir[i]表示的方向没有墙 
            {
                vis[x][y] = true;
                que.push(Node(x, y));
                sn++;  
            }
            a /= 2;
        }
    }
    return sn;
}
int main()
{   
    cin >> m >> n;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> mp[i][j];
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(vis[i][j] == false)
            {
                mx = max(mx, bfs(i, j));//更新房间最大格子数 
                num++;//每成功进行一次广搜，房间数（连通块数）加1 
            }
        }
    cout << num << endl << mx;
    return 0;
}