2 shunfurh shunfurh 于 2017.09.17 16:50 提问

Lattice Animals

Description

Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyominoes. Polyomino is usually represented as a set of sidewise connected squares. Polyomino with n squares is called n-polyomino.
In this problem you are to find a number of distinct free n-polyominoes that fit into rectangle w*h. Free polyominoes can be rotated and flipped over, so that their rotations and mirror images are considered to be the same.
For example, there are 5 different pentominoes (5-polyominoes) that fit into 2*4 rectangle and 3 different octominoes (8-polyominoes) that fit into 3 * 3 rectangle.

Input

The input consists of a single line with 3 integer numbers n, w, and h (1 <= n <= 10, 1 <= w, h <= n).
Output

Write to the output a single integer number -- the number of distinct free n-polyominoes that fit into rectangle w * h.
Sample Input

5 5 5
Sample Output

12

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.01 04:19
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Uva 1602 Lattice Animals (网格动物)
The Solution Of Uva 1602 Lattice Animals (网格动物)题目地址UVa 原地址 VJudge题目大意给定一个 w * h 的 矩阵,在矩阵中找不同连通块的个数(旋转,翻转,平移算作一种)题目做法判重编码判重无疑是这道题的重点。那么从判重的方法来看,有两种方法: STL 的 set 手写 hash 从时间来看,set 所消耗的时间肯定更多,但是更加的方便。那么用
UVa1602 - Lattice Animals
输入n,w,h(1 回溯求解,首先确定搜索对象,格子连通,所以把连通块作为搜索对象,每次枚举一个位置,然后放一个新的块,最后重判。 每个连块会被枚举很多次,有方法可以确保每个n连块恰好被枚举一次。 用函数generate()把每种情况枚举出来。 #include #include #include #include using namespace std; struct Cell {
UVa 1602 Lattice Animals
Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyominoes. Polyomino is usually represent
Lattice Animals UVA - 1602
利用打表法,首先将所有的情况全部计算出来,然后直接查表就可以了。所谓的旋转翻转其实都可以转化为原来位置依次旋转90度以及先翻转得到新的状态,然后依次旋转90度就行了。具体实现见如下代码: #include #include #include #include #include #include #include #include #include #include #include #inclu
1602 - Lattice Animals
Lattice animal is a set of connectedsites on a lattice. Lattice animals on a square lattice are especially popularsubject of study and are also known as polyominoes. Polyomino is usuallyrepresented as
UVA 1062 Lattice Animals
P3870网格动物 时间限制 : - MS   空间限制 : 165536 KB 评测说明 : 3s 问题描述 网格动物是一种在网格中的联通块,由n个方块构成的联通块称为n连块。平移、旋转、翻转之后相同的算作同一种。例如,2*4里面的5连块有5种(第一行),3*3里的8连块有3种(第二行)。
Lattice Animals UVa1602
题意:由n个方格可以组成不同形状的连通块,经过平移、旋转k*90°、翻转操作能够重合的两个连通块视为同一种。给定整数n, w, h, 求能够放进w*h的矩形内的n连通块种数。原题:https://uva.onlinejudge.org/external/16/1602.pdf分析:1.数据结构:定义结构体point{int x,y}表示方格;类lattice{set&amp;lt;point&amp;gt;}表示...
uva 1602 Lattice Animals
题目:Lattice Animals 思路: dfs。 搜索时,每一次都在上一次的图形上加一个方块,具体方法是遍历上一次的图形,在每一个方块的上下左右都尝试放一个方块。 每次搜得一个图形,就将它化为一个标准型式,即整个图形都在第一象限且过原点。然后将这个新的图形翻折、旋转,并把这些变形存进一个set里便于判重。 注意: 只需搜索一次,处理出所有权情况并打表,这可以节省不
UVa 1602:Lattice Animals(BFS)
题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=841&page=show_problem&problem=4477 题意:输入n,w,h(1≤n≤10,1≤w,h≤n)(1 \le n \le 10, 1 \le w, h \le n),求能放在w∗hw*h网格里的不同n连块
woj1005 - Holding Animals
Description The total available floor space on the ark would have been over 100,000 square feet, which would be more floor space than in 20 standard sized  basketball courts. But in our story, we