🧠 题解（Solution）

✅ 本质分析

这个问题可以转化为一个图的连通分量问题，每个模块代表一个图中的节点，相邻的模块之间由墙壁连接，问题就是求出图中的连通分量，即房间的数量。

地图与墙壁关系：

每个模块有四个方向的墙壁，若两个模块在某个方向上没有墙壁隔开，它们是连通的，可以算作一个房间的一部分；

要遍历整个地图，找到每个连通分量，并计算每个连通分量的面积。

✅ 解题思路：

图的表示：

每个模块是一个节点；

相邻模块之间通过不封闭的墙壁（无墙）连接。

深度优先搜索（DFS）或广度优先搜索（BFS）：

使用 DFS/BFS 来找到每个房间的所有模块，并计算该房间的面积；

需要处理不同模块之间的墙壁限制。

具体步骤：

根据输入构建一个二维数组表示地图，每个模块包含一个数字，表示其墙壁情况；

使用 DFS 或 BFS 搜索所有连通的模块，标记并统计每个房间的面积；

输出房间的总数和最大房间的面积。

✅ 详细步骤：

墙壁解析：

将每个模块的墙壁情况转换为图的边，处理相邻模块的连通性；

判断相邻的模块是否有共享墙壁，若没有则它们是连通的；

深度优先搜索（DFS）：

对每个未访问的模块，使用 DFS 寻找该模块所在的连通区域，并计算该区域的模块数量，即为一个房间的面积；

标记每个模块已被访问，避免重复计算。

输出结果：

房间数即为 DFS 中连通分量的个数；

最大房间的面积即为所有连通分量中面积最大的一个。

✅ 算法复杂度分析：

对于每个模块和每条墙壁的处理需要遍历一次，复杂度为 O ( m × n ) O(m×n)，其中 m m 和 n n 分别是城堡的行数和列数；

每次 DFS 遍历一个连通区域，最坏情况下需要遍历所有模块，因此总时间复杂度为 O ( m × n ) O(m×n)。

🧮 示例分析（输入数据 1）：

在这个输入中，4 行 7 列的地图有如下墙壁配置：

第一个房间是一个较大的连通区域，占据 9 9 个模块；

还有 4 4 个较小的房间，分别占据其他模块。

最终输出房间数是 5 5，最大房间面积是 9 9。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 50+10;
int map[maxn][maxn];
bool used[maxn][maxn];
int n,m;

void dfs(int x, int y, int &k)
{
	if((map[x][y] & 2) == 0)
	{
		if(used[x-1][y] == false && x-1 >= 0 && y >= 0 && x-1 < n && y < m)
		{
			k++;
			used[x-1][y] = true;
			dfs(x-1, y,k);
		}
	}
	if((map[x][y] & 8) == 0)
	{
		if(used[x+1][y] == false && x+1 >= 0 && y >= 0 && x+1 < n && y < m)
		{
			k++;
			used[x+1][y] = true;
			dfs(x+1, y, k);
		}
	}
	if((map[x][y] & 1) == 0)
	{
		
		if(used[x][y-1] == false && x >= 0 && y-1 >= 0 && x < n && y-1 < m)
		{ 
			k++;
			used[x][y-1] = true;
			dfs(x, y-1, k);
		}
	}
	if((map[x][y] & 4) == 0)
	{
		
		if(used[x][y+1] == false && x >= 0 && y+1 >= 0 && x < n && y+1 < m)
		{
			k++;
			used[x][y+1] = true;
			dfs(x, y+1, k);
		}
	}
	return;
}

int main()
{
	scanf("%d%d",&n, &m);
	int r;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			scanf("%d",&map[i][j]);
			used[i][j] = false;
		}
	}
	int count = 0;
	int max_a = 0;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(used[i][j] == false)
			{
				used[i][j] = true;
				int k = 1;
				dfs(i, j, k);
				max_a = max(max_a, k);
				count ++;
			}   
		}   
	}   
	printf("%d\n%d\n",count, max_a);
	return 0;
}

🧠 题解（Solution）

✅ 本质分析

这个问题可以转化为一个图的连通分量问题，每个模块代表一个图中的节点，相邻的模块之间由墙壁连接，问题就是求出图中的连通分量，即房间的数量。

地图与墙壁关系：

每个模块有四个方向的墙壁，若两个模块在某个方向上没有墙壁隔开，它们是连通的，可以算作一个房间的一部分；

要遍历整个地图，找到每个连通分量，并计算每个连通分量的面积。

✅ 解题思路：

图的表示：

每个模块是一个节点；

相邻模块之间通过不封闭的墙壁（无墙）连接。

深度优先搜索（DFS）或广度优先搜索（BFS）：

使用 DFS/BFS 来找到每个房间的所有模块，并计算该房间的面积；

需要处理不同模块之间的墙壁限制。

具体步骤：

根据输入构建一个二维数组表示地图，每个模块包含一个数字，表示其墙壁情况；

使用 DFS 或 BFS 搜索所有连通的模块，标记并统计每个房间的面积；

输出房间的总数和最大房间的面积。

✅ 详细步骤：

墙壁解析：

将每个模块的墙壁情况转换为图的边，处理相邻模块的连通性；

判断相邻的模块是否有共享墙壁，若没有则它们是连通的；

深度优先搜索（DFS）：

对每个未访问的模块，使用 DFS 寻找该模块所在的连通区域，并计算该区域的模块数量，即为一个房间的面积；

标记每个模块已被访问，避免重复计算。

输出结果：

房间数即为 DFS 中连通分量的个数；

最大房间的面积即为所有连通分量中面积最大的一个。

✅ 算法复杂度分析：

对于每个模块和每条墙壁的处理需要遍历一次，复杂度为 $O(m \times n)$，其中 $m$ 和 $n$ 分别是城堡的行数和列数；

每次 DFS 遍历一个连通区域，最坏情况下需要遍历所有模块，因此总时间复杂度为 $O(m \times n)$。

🧮 示例分析（输入数据 1）：

在这个输入中，4 行 7 列的地图有如下墙壁配置：

第一个房间是一个较大的连通区域，占据 $9$ 个模块；

还有 $4$ 个较小的房间，分别占据其他模块。

最终输出房间数是 $5$，最大房间面积是 $9$。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 50+10;
int map[maxn][maxn];
bool used[maxn][maxn];
int n,m;

void dfs(int x, int y, int &k)
{
    if((map[x][y] & 2) == 0)
    {
        if(used[x-1][y] == false && x-1 >= 0 && y >= 0 && x-1 < n && y < m)
        {
            k++;
            used[x-1][y] = true;
            dfs(x-1, y,k);
        }
    }
    if((map[x][y] & 8) == 0)
    {
        if(used[x+1][y] == false && x+1 >= 0 && y >= 0 && x+1 < n && y < m)
        {
            k++;
            used[x+1][y] = true;
            dfs(x+1, y, k);
        }
    }
    if((map[x][y] & 1) == 0)
    {
        
        if(used[x][y-1] == false && x >= 0 && y-1 >= 0 && x < n && y-1 < m)
        { 
            k++;
            used[x][y-1] = true;
            dfs(x, y-1, k);
        }
    }
    if((map[x][y] & 4) == 0)
    {
        
        if(used[x][y+1] == false && x >= 0 && y+1 >= 0 && x < n && y+1 < m)
        {
            k++;
            used[x][y+1] = true;
            dfs(x, y+1, k);
        }
    }
    return;
}

int main()
{
    scanf("%d%d",&n, &m);
    int r;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            scanf("%d",&map[i][j]);
            used[i][j] = false;
        }
    }
    int count = 0;
    int max_a = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(used[i][j] == false)
            {
                used[i][j] = true;
                int k = 1;
                dfs(i, j, k);
                max_a = max(max_a, k);
                count ++;
            }   
        }   
    }   
    printf("%d\n%d\n",count, max_a);
    return 0;
}