城堡问题—dfs

首先这一题的难度不是很大，但是也要用到位运算的知识，这个让我想到之前学的位运算遍历，这里也是用位运算来判断一个点墙的数目。这题思路会有点不好找，但是整体题目难度并不大，适合深搜的入门。

图（一）是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m?n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
Input程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。Output城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
Sample Input
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
Sample Output

5
9

解题思路：

1，把方块看成是结点，相邻两个方块之间如果没有墙，则在方块之间连一条边，这样城堡就能转化成一个图。

2，求房间的个数，实际就是求图中有多少个极大连通子图。

3，一个连通子图，往里头加任何一个图里其他点，就会变得不连通，那么这个连通子图就是极大连通子图。

这个其实我更喜欢叫做染色法（就是我之前有看过floodfill漫水填充法就是类似的原理），把相连的房间用相同的数字填充就充当了染色的作用。

还有一个很重要在我看来也是这一题最难的一部分就是怎么描述墙的状态与相连情况。这个地方使用位运算。

输入的每一个方块的值就是墙的数字之和，而1，2，4，8，刚好是二进制中只有一位是1后面都是零的数字，所以这些数字相加就是相当于位运算中的与运算，如果与的结果是1说明有该墙。如果结果是0就说明没有该墙。没有墙就说明相连了，相连了就说明可以往下搜索了（有点啰嗦）。

代码：

#include 
using namespace std;
int r, c;//行数和列数
int rooms[60][60];//这个是用来储存城堡信息的
int color[60][60];//方块是否染色了
int maxRoomArea = 0;//记录房间的最大大小
int roomNum = 0;//记录房间的数量
int roomArea;//记录房间的大小
void Dfs(int i, int k) {
    //如果是旧点（已经染色了）就返回就好了
    if (color[i][k]) {
        return;
    }
    //后面就是把旧点换成新点就好了
    ++roomArea;
    color[i][k] = roomNum;
    //这一步其实也叫做染色
    //后面的步骤其实就是走到与这个点相邻的，在这题中这个条件其实就是没有墙来阻挡
    if ((rooms[i][k] & 1) == 0) Dfs(i, k - 1);//没有西墙，往西边走
    if ((rooms[i][k] * 2) == 0) Dfs(i - 1, k);//没有北墙，往北走
    if ((rooms[i][k] & 4) == 0) Dfs(i, k + 1);//没有东墙，往东走
    if ((rooms[i][k] & 8) == 0) Dfs(i + 1, k);//没有南墙，往南走。
}
int main( ) {
    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> rooms[i][j];
            //输入城堡的信息
        }
    }
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            //首先是没有标记过的话（用color来看）
            //如果color是0的话就说明没有标记过
            if (!color[i][j]) {
                ++roomNum;
                roomArea = 0;
                Dfs(i, j);
                //深度优先搜索把所有连在一起的房间装在一起
                maxRoomArea = max(roomArea, maxRoomArea);//更新最大的房间大小啊。


            }
        }
    }
    cout << roomNum << endl;
    cout << maxRoomArea << endl;
    return 0;
}

后面就根据这个题目来总结一下深搜的基本形式把！其实这题好像还不需要用邻接表或者临界矩阵来储存，因为这题数据是有保证的，保证是有墙的。数组中每一个点都是有用的（这样说有一点怪哦）。

算法与题目积累

城堡问题—dfs

相关

标签