OJ 40 潘多拉星球的悬浮公寓__深搜

2019-11-14 09:18:45

字体：大中小

来源：转载

供稿：网友

描述

在潘多拉星球，纳威人也热衷于搞房地产卖给中国人。他们把空中的悬浮山切割成一个个的立方体，然后在上面盖房子。一个立方体就是一个公寓楼。在悬浮山的表面上，重力是朝向山体中心的，因此每个面都有能住人的房间。作为到处投资的中国IT新贵，你看上了一座悬浮公寓，想知道这个公寓里面有多少个房间，以及最大的房间有多大。自己写个程序解决这个问题吧。

立方体的每个面被划分为k*k(k<20)个方格，方格有可能是平地，也有可能墙，墙无法通过。连续的平地可以形成房间。房间可以跨越棱线。

这里写图片描述

平地用0表示，墙用1表示。

输入

输入第一行为测试数据组数。对每组测试数据：输入第一行为k，接下来为6*k行，每行k个字符(空格分开，平地用0表示，墙用1表示)，分别表示ABDC，BFHD，FEGH，EACG，EFBA，GHDC这6个平面。每个平面第一个字母是左上角，第二个字母是右上角。

输出

输出房间个数和最大的房间大小(包含的平地格子数目)

样例输入

1 3 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0

样例输出

6 12

分析

遍历每个未访问的点查找最大房间，具体实现分析可看此文章： http://blog.csdn.net/pku_zzy/article/details/51648457 在代码中多加了点日志。

实现

#include <iostream>#include <cstring>using namespace std;int a[6][20][20];int n, area = 0;int d[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //udlrint nextSides[6][4] = { { 4,5,3,1 },{ 4,5,0,2 },{ 4,5,1,3 },{ 4,5,2,0 },{ 2,0,3,1 },{ 2,0,3,1 } }; //按题中面的顺序标号。void dfs(int side, int i, int j) { if (a[side][i][j]) return; area++; a[side][i][j] = 1; for (int k = 0; k < 4; k++) { int newI = i + d[k][0]; int newJ = j + d[k][1]; //fix (newI, newJ). int newSide = side; //当前所在面可以左、右扩展搜索。 if (!(side == 4 || side == 5)) { if (newJ < 0) { newSide = nextSides[side][2]; newJ = n - 1; } //搜到左侧一面，置纵坐标新的一面的最右端。 if (newJ >= n) { newSide = nextSides[side][3]; newJ = 0; } //搜到右侧一面，置纵坐标新的一面的最左端。 } if (!(side == 1 || side == 3)) { if ((newI < 0 || newI >= n) && side == 2) { newJ = n - 1 - newJ; } //面2因为是反面，所以需要翻转坐标。 if (newI < 0) newSide = nextSides[side][0], (side == 2 || side == 4) ? newI = 0 : newI = n - 1; if (newI >= n) newSide = nextSides[side][1], (side == 0 || side == 5) ? newI = n - 1 : newI = 0; if (newSide != side && newSide == 2) newJ = n - 1 - newJ; } if (!(side == 0 || side == 2)) { switch (side) { case 4: if (newJ < 0) newSide = nextSides[side][2], newJ = newI, newI = 0; if (newJ >= n) newSide = nextSides[side][3], newJ = n - 1 - newI, newI = 0; break; case 5: if (newJ < 0) newSide = nextSides[side][2], newJ = newI, newI = n - 1; if (newJ >= n) newSide = nextSides[side][3], newJ = n - 1 - newI, newI = n - 1; break; case 1: if (newI < 0) newSide = nextSides[side][0], newI = n - 1 - newJ, newJ = n - 1; if (newI >= n) newSide = nextSides[side][1], newI = n - 1 - newJ, newJ = n - 1; break; case 3: if (newI < 0) newSide = nextSides[side][0], newI = newJ, newJ = 0; if (newI >= n) newSide = nextSides[side][1], newI = newJ, newJ = 0; break; } } if (!a[newSide][newI][newJ]) { dfs(newSide, newI, newJ); } }}int main() {// freopen("in.txt", "r", stdin); int cases; cin >> cases; while (cases--) { cin >> n; for (int side = 0; side < 6; side++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[side][i][j]; } } } int num = 0, maxArea = 0; for (int side = 0; side < 6; side++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!a[side][i][j]) { num++; area = 0; dfs(side, i, j); if (area > maxArea) { maxArea = area; } } } } } cout << num << " " << maxArea << endl; } return 0;}

上一篇：LeetCode 155. Min Stack

下一篇：PAT B1027. 打印沙漏(20)