[LA][正方體展開圖&窮舉] 6210 - Beauty of Regular Polyhedron＠Morris' Blog

2013-10-20 09:47:20| 人氣3,029| 回應0 | 上一篇 | 下一篇

[LA][正方體展開圖&窮舉] 6210 - Beauty of Regular Polyhedron

推薦 0 收藏 0 轉貼0 訂閱站台

It is quite easy to draw regular polygons but what about regular polyhedron? If you are allowed to cut papers and join them to form regular polyhedron it would be easy task, but what if I tell you to fold papers to form polyhedron? Let me clear you by a picture excerpt from Wikipedia.

Left side paper can be folded to form an octahedron. If you don't know how an octahedron looks like, it is shown in the right side.

However you don't need to be scared seeing the octahedron. We will work with the simplest of all polyhedron, regular hexahedron. Actually regular hexahedron is formal name of cube. Let's look at the following pictures:

Left side paper can be folded to a cube. There are many other shapes of six connected squares which can be folded to form a cube.

In this problem you will be given a grid. It will be a RxC rectangle which is divided into unit squares. A square will look like one of the following:

So a 2 x 2 grid may look the left diagram below (which as input to your program will be given as right one. You will find the meaning of the numbers in the above picture):

In how many ways can you cut 6 connected squares from the given RxC grid so that when a cube is formed folding them, the lines on the cube surfaces form a single loop? For example, if we cut out the left portion from a grid in the diagram below it will form a valid cube, but if we cut out the right portion, we can fold it to form a cube but the lines on the surfaces will not form a single loop. So it is not valid.

Note that, the lines on the grid are in both sides and the lines in both the sides are same. So you don't need to worry which side of the grid square is inside cube.

Input

First line of the test case contains a positive integer T ( T

100). Hence follows T test cases. Each test case starts with 2 positive integer R and C denoting number of rows and number of columns in grid respectively ( 1

R, C

20). Then there will be R lines of C integers. Each integer will range from 0 to 5 (meaning of each of the number is given in the problem statement).

Output

For each case, output the case number followed by the answer to the query in the problem description.

Sample Input

Sample Output

Case 1: 1
Case 2: 4
Case 3: 0

題目描述：

給一張圖，每個格子上都有圖案，而問如果正方體在其平面上展開，共有多少種可以使得這個正方體只存在一個
單獨的 loop。

題目解法：

展開圖共有 11 種 (去除同構)，藉由旋轉鏡射找到所有匹配可能，並且對於匹配成功的檢查是否只有一個環。

img[][] => 表示數字可以連接的上下左右資訊。
kdir[][] => 表示 11 種中，ABCDEF 個別上下左右連接著誰。
weight[] => 由於某些展開圖鏡射會相同，或者旋轉會類同，因此考慮將其加上權重去重複。

不考慮將 11 種展開圖旋轉鏡射，而是對於原圖做，因此要將盤面上的數字做轉換。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char img[6][5] = {//[number][up,right,down,left]
	"1010","0101","1001","1100","0110","0011"
};
int wcnt[11];
int weight[11] = {2,1,1,2,2,2,1,1,1,2,2};
char kdir[11][6][5] = {// [up, right, down, left]
    {"EBFD","ECFA","EDFB","EAFC","CBAD","ABCD"},
    {"EBFD","ECFA","EDFB","EAFC","CBAD","BCDA"},
    {"EBFD","ECFA","EDFB","EAFC","CBAD","CDAB"},
    {"EBFD","ECFA","EDFB","EAFC","CBAD","DABC"},
    {"EBFD","ECFA","EDFB","EAFC","DCBA","BCDA"},
    {"EBFD","ECFA","EDFB","EAFC","DCBA","CDAB"},
    {"EBFD","ECFA","EDFB","CEAF","CBAD","ABCD"},
    {"EBFD","ECFA","EDFB","CEAF","CBAD","BCDA"},
    {"EBFD","ECFA","EDFB","CEAF","CBAD","CDAB"},
    {"EBFD","ECFA","EDFB","CEAF","CBAD","CDAB"},
    {"EBFD","ECFA","BEDF","CEAF","CBAD","BCDA"},
};
char kind[11][4][6] = {
    {"E0000",
     "ABCD0",
     "F0000"},
    {"E0000",
     "ABCD0",
     "0F000"},
    {"E0000",
     "ABCD0",
     "00F00"},
    {"E0000",
     "ABCD0",
     "000F0"},
    {"0E000",
     "ABCD0",
     "0F000"},
    {"0E000",
     "ABCD0",
     "00F00"},
    {"DE000",
     "0ABC0",
     "0F000"},
    {"DE000",
     "0ABC0",
     "00F00"},
    {"DE000",
     "0ABC0",
     "000F0"},
    {"FDE00",
     "00ABC",
     "00000"},
    {"DE000",
     "0AB00",
     "00FC0"},
};
void rotate(int g[][20], int &n, int &m) {//clockwise
    int i, j, t[20][20];
    int mapped[6] = {1,0,3,4,5,2};
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
        	t[j][n-1-i] = mapped[g[i][j]];
    swap(n, m);
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            g[i][j] = t[i][j];
}
void upturn(int g[][20], int &n, int &m) {
    int i, j, t[20][20];
    int mapped[6] = {0,1,3,2,5,4};
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
        	t[i][m-1-j] = mapped[g[i][j]];
        }
    }
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            g[i][j] = t[i][j];
}
int check(int g[][20], int n, int m) {
    int i, j, p, q, k;
    int ret = 0;
    int num[6];
    /*for(i = 0, puts("-"); i < n; i++, puts("")) {
    	for(j = 0; j < m; j++)
    		printf("%d ", g[i][j]);
    }*/
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            for(k = 0; k < 11; k++) {
                for(p = 0; p < 3; p++)
                    for(q = 0; q < 5; q++) {
                        if(kind[k][p][q] == '0')
                            continue;
                        if(i+p >= n || j+q >= m)
                            p = 10, q = 10;
                        num[kind[k][p][q]-'A'] = g[i+p][j+q];
                    }
                if(p == 3) {
                	int used = 0;//ABCDEF
                	int start = 0, prev = -1;
                	int a, b, c;
                	int TYPE;/*
                	printf("%d ---- %d %d\n", k, i, j);
                	puts(kind[k][0]);
                	puts(kind[k][1]);
                	puts(kind[k][2]);*/
                	/*for(a = 0; a < 6; a++)
                		printf("%d ", num[a]);
                	puts("");*/
                	int flag;
                	for(a = 0; a < 7; a++) {
                	/*	if(i == 0 && j == 0)
                			printf("> %d %d\n", start, num[start]);*/
                		used |= 1<<start;
                		TYPE = num[start];
                		flag = 0;
                		for(p = 0; p < 4; p++) {
                			if(img[TYPE][p] == '1') {
                				if(prev == kdir[k][start][p]-'A')
                					flag = 1;
                			}
                		}
                		if(flag == 0 && start != 0 || a == 6)	break;
                		for(p = 0; p < 4; p++) {
                			if(img[TYPE][p] == '1') {
                				if(prev != kdir[k][start][p]-'A') {
                					prev = start;
                					start = kdir[k][start][p]-'A';
                					break;
                				} 
                			}
                		}
                	}
                	if(used == 63 && start == 0 && flag == 1) {
                		ret++;
                		wcnt[k]++;
						//printf("TYPE %d %d %d %d\n", k, i, j, start);
					}
                }
            }
        }
    }
    //printf("%d\n", ret);
    return ret;
}
int sol(int g[][20], int n, int m) {
    int i, j;
    int ret = 0;
    for(i = 0; i < 2; i++) {
        for(j = 0; j < 4; j++) {
        	//printf("%d\n", j);
        	ret += check(g, n, m);
        	//break;
            rotate(g, n, m);
        }
        //break;
        upturn(g, n, m);
    }
    return ret;
}
int main() {
	/*freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);*/ 
	int i, j, n, m;
    int cases = 0, testcase;
    int g[20][20];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
        memset(wcnt, 0, sizeof(wcnt));
		sol(g, n, m);
		int ret = 0;
		for(i = 0; i < 11; i++) {
			ret += wcnt[i]/weight[i];
			//printf("%d %d\n", wcnt[i], wcnt[i]/weight[i]);
			if(wcnt[i]%weight[i]) {
				puts("err");
			}
		}
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
3
3 4
0 0 3 0
3 1 5 0
0 0 3 0
3 4
0 0 3 4
3 1 5 0
0 0 3 2
3 4
0 0 3 0
2 4 5 3
0 0 2 0

3
5 5
1 3 5 0 1
1 5 3 3 3
4 5 4 2 4
5 3 2 3 2
5 2 5 3 3
5 5
1 2 2 5 5 
4 4 3 1 4 
1 3 5 2 2 
2 1 2 0 5 
2 2 5 5 2 
*/

我要檢舉

#6210#Beauty of Regular Polyhedron#LA#正方體展開圖#窮舉

台長： Morris

您可能對以下文章有興趣

[UVA][Math] 1264 - Binary Search Tree

[UVA] 1208 - Oreon

[UVA][dp] 976 - Bridge Building

[UVA] 201 - Squares

人氣(3,029) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][SSSP] 11374 - Airport Express
此分類上一篇:[LA] 6288 - Labyrinth of the Minotaur

回應(0)