The Castle OpenJ_Bailian - 1164

本文主要是介绍The Castle OpenJ_Bailian - 1164，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

The Castle OpenJ_Bailian - 1164

     1   2   3   4   5   6   7  
   #############################
#   |   #   |   #   |   |   #
   #####---#####---#---#####---#
#   #   |   #   #   #   #   #
   #---#####---#####---#####---#
#   |   |   #   #   #   #   #
   #---#########---#####---#---#
#   #   |   |   |   |   #   #
   #############################
(Figure 1)

#  = Wall   
|  = No wall
-  = No wall

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/4/8 刚好是 二进制 0000 数 在对应位为 1，所以 可以通过采用 该数字与 1， 2，4，8做与运算的方式来判断结点之间是否连通

完整代码如下：

#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;


// n*m个单位房间
int n, m;
int room[51][51];
int vis[51][51];

bool inArea(int x, int y)
{
    return (x >= 0 && y >= 0 && x < n && y < m);
}

int area;
void dfs(int i, int j)
{
    vis[i][j] = 1;
    area++;
    if (((room[i][j] & 1) == 0) && inArea(i, j - 1) && !vis[i][j - 1]) dfs(i, j - 1);　　// 西面墙，对应了向西探索是否连通
    if (((room[i][j] & 2) == 0) && inArea(i - 1, j) && !vis[i - 1][j]) dfs(i - 1, j);　　// 北面墙，对应了向北探索是否连通
    if (((room[i][j] & 4) == 0) && inArea(i, j + 1) && !vis[i][j + 1]) dfs(i, j + 1);　　// 东面墙,对一个了向东探索是否连通
    if (((room[i][j] & 8) == 0) && inArea(i + 1, j) && !vis[i + 1][j]) dfs(i + 1, j);　　// 南面墙，对应了向南探索是否连通
}


int main()
{
    // freopen("in.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) != EOF)
    {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                scanf("%d", &room[i][j]);
            }
        }

        int roomCnt = 0;
        int maxRoomArea = -1;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (!vis[i][j])
                {
                    roomCnt++;
                    area = 0;
                    dfs(i, j);
                    if (maxRoomArea < area)
                        maxRoomArea = area;
                }

            }
        }

        cout << roomCnt << endl << maxRoomArea << endl;
    }


    return 0;
}

这篇关于The Castle OpenJ_Bailian - 1164的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！