测评请前往##Luogu##

题目背景

魔方大厦是个神奇的地方，王小一和他的同学们收到了一个陌生人的电话，告诉他们可以将大厦里面的房间分配给每一个人。作为一个时时刻刻都被同桌欺负的人，这可是个天大的扬眉吐气的好消息，于是他背上行囊准备出发。

题目描述

魔方大厦是一个边长为n的立方体。以它的一个顶点房间坐标为(0,0,0)(0,0,0)，以对角线顶点房间坐标为(n−1,n−1,n−1)(n-1,n-1,n-1)建立坐标系。每个房间可能在6个方向有门，如果一个房间向上有门并且它上面的房间向下也有门就看作是一个房间。其他方向同理。王小一想知道魔方大厦的房间够不够他和他的同学分，并且里面最大房间的体积是多少**(以一个没有门的房间体积为1)**。不考虑有门通向魔方大厦外的情况。

输入输出格式

输入格式

  • 第一行是2个整数，n和k，分别表示魔方大厦的边长和王小一的同学个数。
  • 随后n3n^3行，每一行九个数据，前三个数据x,y,zx,y,z表示当前房间的坐标(x,y,z)(x,y,z)，后六个数据a,b,c,d,e,fa,b,c,d,e,f分别表示当前房间在 向x轴正方向，向x轴负方向，向y轴正方向，向y轴负方向，向z轴正方向，向z轴负方向 上有没有门可以通过。值为1表示可以通过，为0则不能。

输出格式

输出一共一行，包括一个字符串和一个正整数。字符串为"Yes"或"No"，表示房间数够不够王小一和他的同学分；随后一个空格；正整数为最大房间的体积。

输入输出样例

输入样例#1:

2 0
0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0
0 1 0 1 0 0 1 1 0
0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 0

输出样例#1:

Yes 4

输入样例#2:

2 6
0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0
0 1 0 1 0 0 1 1 0
0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 0

输出样例#2:

No 4

说明

样例说明

数据说明

  1. 对于前10%的数据，保证n<10，k=0k = 0；
  2. 对于前30%的数据，保证n<20，对于10%~30%的数据，保证 k>n3k > n^3；
  3. 对于前100%的数据，保证n<50；

标程

标程#1 - CHY - [并查集]

#include <bits/stdc++.h>
using namespace std;

struct room
{
    int x, y, z;
    room(int a, int b, int c) : x(a), y(b), z(c) {}
    bool operator==(const room &r)
    {
        return this->x == r.x && this->y == r.y && this->z == r.z;
    }
    //覆写==运算符，后面会用
    void operator=(const room &r)
    {
        this->x = r.x;
        this->y = r.y;
        this->z = r.z;
    }
    //覆写=赋值运算符，后面会用

};
//为了构建father数组

struct Check
{
    bool is_fx, is_bx, is_fy, is_by, is_fz, is_bz;
    Check()
    {
        is_fx = is_bx = is_fy = is_by = is_fz = is_bz = false;
    }
};
//某一个房间的门的情况

vector<vector<vector<room>>> father;//并查集father
vector<vector<vector<Check>>> check;//为了合并操作存储的每一个房间的门
vector<vector<vector<int>>> volume;//存储并查集元素数(体积)

int max_volume = 1;//最大体积
int n = 0;//大厦边长

void init()
{
    for (int i = 0; i < n; i++)
    {
        vector<vector<room>> t;
        vector<vector<Check>> f;
        vector<vector<int>> c;
        for (int j = 0; j < n; j++)
        {
            vector<room> a;
            vector<Check> b(n);
            vector<int> h(n, 1);
            for (int k = 0; k < n; k++)
            {
                room r(i, j, k);
                a.push_back(r);
            }
            t.push_back(a);
            f.push_back(b);
            c.push_back(h);
        }
        volume.push_back(c);
        check.push_back(f);
        father.push_back(t);
    }
}
//初始化father每一项为自己，check全部为false，体积全为1

room find(room a)
{
    if (father[a.x][a.y][a.z] == a)
        return a;
    else
        father[a.x][a.y][a.z] = find(father[a.x][a.y][a.z]);
    return father[a.x][a.y][a.z];
}
//并查集find基本逻辑
//如果我爸是我就返回我
//否则我爷爷就是我爸爸

void merge(int ax, int ay, int az, int bx, int by, int bz)
{
    room x(ax, ay, az);
    room y(bx, by, bz);
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    father[x.x][x.y][x.z] = y;
    //并查集merge基本逻辑
    //找我和你爸爸
    //如果一个爸就不管
    //否则你爸就是我爷爷

    volume[y.x][y.y][y.z] += volume[x.x][x.y][x.z];//元素个数(体积)更新
    max_volume = max(max_volume, volume[y.x][y.y][y.z]);//每次合并取最大
}
//并查集合并

int count_of_rooms()
{
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                if (father[i][j][k].x == i && father[i][j][k].y == j && father[i][j][k].z == k)
                    ans++;
    return ans;
}
//最后爸爸的总个数就是房间个数

void merge_room()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (i < n - 1 && check[i][j][k].is_fx && check[i + 1][j][k].is_bx)
                    merge(i, j, k, i + 1, j, k);
                if (i > 0 && check[i][j][k].is_bx && check[i - 1][j][k].is_fx)
                    merge(i, j, k, i - 1, j, k);

                if (j < n - 1 && check[i][j][k].is_fy && check[i][j + 1][k].is_by)
                    merge(i, j, k, i, j + 1, k);
                if (j > 0 && check[i][j][k].is_by && check[i][j - 1][k].is_fy)
                    merge(i, j, k, i, j - 1, k);

                if (k < n - 1 && check[i][j][k].is_fz && check[i][j][k + 1].is_bz)
                    merge(i, j, k, i, j, k + 1);
                if (k > 0 && check[i][j][k].is_bz && check[i][j][k - 1].is_fz)
                    merge(i, j, k, i, j, k - 1);
            }
        }
    }
}
//合并房间的条件逻辑
//到没到边界? 是否联通?

void read_room()
{
    int x, y, z;
    short fx, bx, fy, by, fz, bz;
    for (int i = 0; i < n * n * n; i++)
    {
        cin >> x >> y >> z;
        cin >> fx >> bx >> fy >> by >> fz >> bz;
        if (fx == 1)
            check[x][y][z].is_fx = true;
        if (bx == 1)
            check[x][y][z].is_bx = true;
        if (fy == 1)
            check[x][y][z].is_fy = true;
        if (by == 1)
            check[x][y][z].is_by = true;
        if (fz == 1)
            check[x][y][z].is_fz = true;
        if (bz == 1)
            check[x][y][z].is_bz = true;
    }
}
//读取数据

int main()
{
    std::ios::sync_with_stdio(false);
    max_volume = 0;
    cin >> n >> k;
    init();//初始化
    read_room();//读房间
    merge_room();//并房间
    int c = count_of_rooms();//查房间
    if (c > k)
        cout << "Yes ";
    else
        cout << "No ";
    cout << max_volume << endl;
    }
    return 0;
}

标程#2 - XBY - [深搜]

#include <bits/stdc++.h>
using namespace std;

int dool[105][105][105][7], vis[105][105][105];
const int mx[] = {1, -1, 0, 0, 0, 0};
const int my[] = {0, 0, 1, -1, 0, 0};
const int mz[] = {0, 0, 0, 0, 1, -1};

int n, k, maxn = 0, cnt = 0;

int num_pair(int i) {
    if(i % 2 == 0) return i + 1;
    return i - 1;
}//查找一个房间的门相对的门

int dfs(int x, int y, int z) {  //如果满足：
    if(vis[x][y][z]             //已经访问
            || x < 0 || x >= n  //已经越界
            || y < 0 || y >= n  //已经越界
            || z < 0 || z >= n) //已经越界
        return 0;               // => 返回0
    int ans = 1;                //初始化ans为1(一个房间体积为1)
    vis[x][y][z] = 1;           //已经访问
    for(int i = 0; i < 6; i++) {//6个方向
        if(dool[x][y][z][i]     //如果可以连通
            && dool[x + mx[i]][y + my[i]][z + mz[i]][num_pair(i)])
        {
            ans += dfs(x + mx[i], y + my[i], z + mz[i]);    //继续递归搜索该房间所连通的房间
        }
    }
    return ans; //返回房间体积
}

int main() {
    cin >> n >> k;
    k++;
    int x, y, z, p, t;
    for(int i = 0; i < pow(n, 3); i++) {
        cin >> x >> y >> z;
        for(int j = 0; j < 6; j++) {
            cin >> p;
            if(p) dool[x][y][z][j] = 1;
        }
    }
    //读取房间和门信息

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int h = 0; h < n; h++) {
                if(t = dfs(i, j, h) != 0) {
                    cnt++;
                    maxn = max(maxn, t);
                }
                //穷举并深搜,取最大体积,记录搜索次数(房间数)
            }
        }
    }

    if(cnt >= k) cout << "Yes ";
    else cout << "No ";
    cout << maxn;
    return 0;
}