UVA 687 - Lattice Practices(暴力枚举+位运算)

Lattice Practices

Once upon a time, there was a king who loved beautiful costumes very much. The king had a special cocoon bed to make excellent cloth of silk. The cocoon bed had 16 small square rooms, forming a 44 lattice, for 16 silkworms. The cocoon bed can be depicted as follows:

UVA 687 - Lattice Practices(暴力枚举+位运算)


The cocoon bed can be divided into 10 rectangular boards, each of which has 5 slits:vcD4KPHA+PC9wPgo8aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20131231/20131231094708216.gif" alt="\">

Note that, except for the slit depth, there is no difference between the left side and the right side of the board (or, between the front and the back); thus, we cannot distinguish a symmetric board from its rotated image as is shown in the following:

UVA 687 - Lattice Practices(暴力枚举+位运算)


Slits have two kinds of depth, either shallow or deep. The cocoon bed should be constructed by fitting five of the boards vertically and the others horizontally, matching a shallow slit with a deep slit.

Your job is to write a program that calculates the number of possible configurations to make the lattice. You may assume that there is no pair of identical boards. Notice that we are interested in the number of essentially different configurations and therefore you should not count mirror image configurations and rotated configurations separately as different configurations.

The following is an example of mirror image and rotated configurations, showing vertical and horizontal boards seperately, where shallow and deep slits are denoted by `1" and `0' respectively.

UVA 687 - Lattice Practices(暴力枚举+位运算)


Notice that a rotation may exchange positions of a vertical board and a horizontal board.

Input

The input consists of multiple data sets, each in a line. A data set gives the patterns of slits of 10 boards used to construct the lattice. The format of a data set is as follows:

xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx

Each x is either `0' or `1'. `0' means a deep slit, and `1' a shallow slit. A block of five slit descriptions corresponds to a board. There are 10 blocks of slit descriptions in a line. Two adjacent blocks are separated by a space.

For example, the first data set in the Sample Input means the set of the following 10 boards:

UVA 687 - Lattice Practices(暴力枚举+位运算)


The end of the input is indicated by a line consisting solely of three characters ``END">

Output

For each data set, the number of possible configurations to make the lattice from the given 10 boards should be output, each in a separate line.

Sample Input

10000 01000 00100 11000 01100 11111 01110 11100 10110 11110 10101 01000 00000 11001 01100 11101 01110 11100 10110 11010 END

Sample Output

40 6

题意:给10块床坂,求可以拼出的种数,旋转对称算一种。

思路:每一块可以用一个2进制数表示,并且拼图是不重复的。所以只要开一个32的数组就能存放拼图了。暴力枚举。枚举5块正放逆放,然后另外5快去判断能不能组成,一开始想总情况直接除以8,结果一直WA,后面改成用SET保存下找到过的方法的对应的8种方法,就过了。。哎,写得很搓,卡了两天了。。

代码:

#include #include #include #include #include using namespace std; const int zhuan[25] = {20, 15, 10, 5, 0, 21, 16, 11, 6, 1, 22 ,17, 12, 7, 2, 23, 18, 13, 8, 3, 24, 19, 14, 9, 4}; const int dui[25] = {4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 14, 13, 12, 11, 10, 19, 18, 17, 16, 15, 24, 23, 22, 21, 20}; const int N = 20; char str[N], sb[30], sbb[30]; int way[N], ans, save[N], saven, v[32], z[32]; set state; void zh(char *a) { char save[30]; for (int i = 0; i = 0; i --) { int s = 0; for (int j = 0; j = 0; i --) { for (int j = 0; j = 0; i--) { if (num >= (1

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:Effective C++(11) 自我赋值(a=a)时会发生什么?
下一篇:POJ 2774 Long Long Message
相关文章

[poj 3090]Visible Lattice Point[

poj3090 Visible Lattice Points

POJ 3090 Visible Lattice Points

POJ 3090 Visible Lattice Points

POJ 3090 Visible Lattice Points

Microsoft.Practices.Unit在Web应用程

Openmp在暴力猜测MD5源字串一例

hdu 1113 暴力以及map string的用法

ZOJ 3465 The Hive 暴力模拟

poj 2870 Light Up 暴力搜索 + 剪枝

图文推荐

UVA 687 - Lattice Practices(暴力枚举+位运算)
ZOJ 3640 Help Me
UVA 687 - Lattice Practices(暴力枚举+位运算)
CF 518C(Anya and
UVA 687 - Lattice Practices(暴力枚举+位运算)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-26 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.069 (s). 10 q(s)