UVA12113-Overlapping Squares（二进制枚举） _overlapping

青春须早为，岂能长少年。这篇文章主要讲述UVA12113-Overlapping Squares（二进制枚举）相关的知识，希望能为你提供帮助。
Problem UVA12113-Overlapping Squares
Accept：116 Submit：596
Time Limit: 3000 mSec

文章图片
Problem Description

文章图片

文章图片
InputThe input consists of several test cases. Each test case is contained in ?ve lines and each line contains nine characters. If the horizontal border of a ?lled square is visible it is denoted with ‘ ’ (ASCII value 95) sign and if vertical border of a ?lled square is visible then it is denoted with ‘|’ (ASCII value 124) character. The board contains no other character than ‘ ’, ‘|’ and of course ‘ ’ (ASCII Value 32). The border lines of the squares can only be along the grid lines. Each board lines end with a ‘#’ (Hash character) which denotes the end of line. This character is not a part of the grid or square. The last test case is followed by a single zero, which should not be processed.

文章图片
OutputFor each test case, print the case number and ‘Yes’ or ‘No’, depending on whether it’s possible to form the target.

文章图片
Sample Input

文章图片

文章图片
Sample OuputCase 1: Yes
Case 2: Yes
Case 3: No
Case 4: Yes

题解：感觉最近做的题都十分考验代码能力（然而我很水），想到一共只有九种摆放方案之后这个题的思维就基本上结束了，所有的挑选方案只有2^9，直接二进制枚举，对于相同的挑选方案，不同的摆放顺序也会带来不同的覆盖结果，解决方法就是next_permutation()，预处理出来不同小正方形的覆盖格子的标号，接下来暴力就好。

1 #include < bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = (1< < 9); 6 const int N = 5,M = 9; 7 const int kind = 9; 8 9 int edge[9][8] = {{1,3,9,13,18,19,21,22}}; 10 int core[9][4] = {{10,11,12,20}}; 11 int bits[kind+1],target[N*M]; 12 13 int read(){ 14char str[20]; 15int cnt = 0,edges = 0; 16for(int i = 0; i < N; i++){ 17gets(str); 18if(str[0] == \'0\') return -1; 19for(int j = 0; j < M; j++){ 20if(str[j] == \' \') target[cnt++] = 0; 21else target[cnt++] = 1,edges++; 22} 23} 24return edges; 25 } 26 27 void init(){ 28for(int i = 0; i < 3; i++){ 29for(int j = 0; j < 3; j++){ 30if(!i & & !j) continue; 31int plus,minus; 32if(j == 0) plus = 9,minus = 3; 33else plus = 2,minus = 1; 34for(int k = 0; k < 8; k++){ 35edge[i*3+j][k] = edge[i*3+j-minus][k]+plus; 36} 37for(int k = 0; k < 4; k++){ 38core[i*3+j][k] = core[i*3+j-minus][k]+plus; 39} 40} 41} 42 } 43 44 int bitcount(int s){ 45return s == 0 ? 0 : bitcount(s> > 1)+(s& 1); 46 } 47 48 void bitpos(int s){ 49int cnt = 0; 50for(int i = 0; i < 9; i++){ 51if(s& (1< < i)) bits[cnt++] = i; 52} 53 } 54 55 int iCase = 1; 56 57 int main() 58 { 59 #ifdef GEH 60freopen("helloworld.01,inp","r",stdin); 61 #endif 62init(); 63int edge_cnt; 64while(edge_cnt=read()){ 65if(edge_cnt == -1) break; 66int tmp[M*N]; 67bool ok = false; 68for(int s = 0; s < maxn; s++){ 69int n = bitcount(s); 70bitpos(s); 71if(n> 6 || n*8< edge_cnt) continue; 72do{ 73memset(tmp,0,sizeof(tmp)); 74for(int i = 0; i < n; i++){ 75for(int j = 0; j < 8; j++){ 76tmp[edge[bits[i]][j]] = 1; 77} 78for(int j = 0; j < 4; j++){ 79tmp[core[bits[i]][j]] = 0; 80} 81} 82 83if(memcmp(tmp,target,sizeof(target)) == 0){ 84ok = true; 85break; 86} 87}while(next_permutation(bits,bits+n)); 88if(ok) break; 89} 90printf("Case %d: ",iCase++); 91if(ok) printf("Yes\\n"); 92else printf("No\\n"); 93} 94return 0; 95 }

【UVA12113-Overlapping Squares（二进制枚举）】