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

2019-11-11 07:53:17

字體：大中小

供稿：網(wǎng)友

描述

在潘多拉星球，納威人也熱衷于搞房地產(chǎn)賣(mài)給中國(guó)人。他們把空中的懸浮山切割成一個(gè)個(gè)的立方體，然后在上面蓋房子。一個(gè)立方體就是一個(gè)公寓樓。在懸浮山的表面上，重力是朝向山體中心的，因此每個(gè)面都有能住人的房間。作為到處投資的中國(guó)IT新貴，你看上了一座懸浮公寓，想知道這個(gè)公寓里面有多少個(gè)房間，以及最大的房間有多大。自己寫(xiě)個(gè)程序解決這個(gè)問(wèn)題吧。

立方體的每個(gè)面被劃分為k*k(k<20)個(gè)方格，方格有可能是平地，也有可能墻，墻無(wú)法通過(guò)。連續(xù)的平地可以形成房間。房間可以跨越棱線。

這里寫(xiě)圖片描述

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

輸入

輸入第一行為測(cè)試數(shù)據(jù)組數(shù)。對(duì)每組測(cè)試數(shù)據(jù)：輸入第一行為k，接下來(lái)為6*k行，每行k個(gè)字符(空格分開(kāi)，平地用0表示，墻用1表示)，分別表示ABDC，BFHD，F(xiàn)EGH，EACG，EFBA，GHDC這6個(gè)平面。每個(gè)平面第一個(gè)字母是左上角，第二個(gè)字母是右上角。

輸出

輸出房間個(gè)數(shù)和最大的房間大小(包含的平地格子數(shù)目)

樣例輸入

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

分析

遍歷每個(gè)未訪問(wèn)的點(diǎn)查找最大房間，具體實(shí)現(xiàn)分析可看此文章： http://blog.csdn.net/pku_zzy/article/details/51648457 在代碼中多加了點(diǎn)日志。

實(shí)現(xiàn)

#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 } }; //按題中面的順序標(biāo)號(hào)。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; //當(dāng)前所在面可以左、右擴(kuò)展搜索。 if (!(side == 4 || side == 5)) { if (newJ < 0) { newSide = nextSides[side][2]; newJ = n - 1; } //搜到左側(cè)一面，置縱坐標(biāo)新的一面的最右端。 if (newJ >= n) { newSide = nextSides[side][3]; newJ = 0; } //搜到右側(cè)一面，置縱坐標(biāo)新的一面的最左端。 } if (!(side == 1 || side == 3)) { if ((newI < 0 || newI >= n) && side == 2) { newJ = n - 1 - newJ; } //面2因?yàn)槭欠疵妫孕枰D(zhuǎn)坐標(biāo)。 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;}

上一篇：Mac OS 安裝Maven

下一篇：lucene總結(jié)