<Sicily>Tiling a Grid With Dominoes
一、题目描述
We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.
Write a program that takes as input the width, W , of the grid and outputs the number of different ways to tile a 4-by-W grid.
二、输入
The first line of input contains a single integer N , (1<=N<=1000) which is the number of datasets that follow.
Each dataset contains a single decimal integer, the width, W , of the grid for this problem instance.
三、输出
For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.
例如
输入:
3
2
3
7
输出:
1 5
2 11
3 781
四、解题思路
1、问题分析
使用无数个1x2的多米诺骨牌去铺满4xn的棋盘,问有多少种不同的覆盖方法。
这道题可以使用动态规划的方法解。
很明显当n等于1时,只有一种方法,也就是两个都是竖着放。
当n>2时,我们使用一个矩阵matrix[n][m]来表示排在第n列的情况。m表示每列的各格的状态,例如该题有4行,所以m表示的是4位只有0、1状态的数(0表示空,1表示排)。2^4=16,应该有16中状态,但是并不是每种状态都能成立。
状态转移:
matrix[i][0] = matrix[i - 1][15];
matrix[i][3] = matrix[i - 1][15] + matrix[i - 1][12];
matrix[i][6] = matrix[i - 1][15] + matrix[i - 1][9];
matrix[i][9] = matrix[i - 1][6];
matrix[i][12] = matrix[i - 1][15] + matrix[i - 1][3];
matrix[i][15] = matrix[i - 1][15] + matrix[i - 1][12] + matrix[i - 1][6] + matrix[i - 1][3] + matrix[i - 1][0];
初始状态:
matrix[1][0] = matrix[1][3] = matrix[1][6] = matrix[1][12] = matrix[1][15] = 1;
状态转移图(灰色表示不填充,橙色表示填充)
1)matrix[i - 1][15] 转移到 matrix[i][0]:
2)matrix[i - 1][15] 转移到matrix[i][3]:
3)matrix[i - 1][12] 转移到matrix[i][3]:
4)matrix[i - 1][15] 转移到matrix[i][6]:
5)matrix[i - 1][9] 转移到matrix[i][6]:
6)matrix[i - 1][6] 转移到matrix[i][9]:
7)matrix[i - 1][15] 转移到matrix[i][12]:
8)matrix[i - 1][3] 转移到matrix[i][12]:
9)matrix[i - 1][15] 转移到matrix[i][15]:
10)matrix[i - 1][12] 转移到matrix[i][15]:
11)matrix[i - 1][6] 转移到matrix[i][15]:
12)matrix[i - 1][3] 转移到matrix[i][15]:
13)matrix[i - 1][0] 转移到matrix[i][15]:
五、代码
#include<iostream>
using namespace std;
int main()
{
int leng = 1000;
int result;
int printNum;
int matrix[leng + 1][16];
matrix[1][0] = matrix[1][3] = matrix[1][6] = matrix[1][12] = matrix[1][15] = 1;
matrix[1][9] = 0;
for(int i = 2; i < leng + 1; i++)
{
matrix[i][0] = matrix[i - 1][15];
matrix[i][3] = matrix[i - 1][15] + matrix[i - 1][12];
matrix[i][6] = matrix[i - 1][15] + matrix[i - 1][9];
matrix[i][9] = matrix[i - 1][6];
matrix[i][12] = matrix[i - 1][15] + matrix[i - 1][3];
matrix[i][15] = matrix[i - 1][15] + matrix[i - 1][12] + matrix[i - 1][6] + matrix[i - 1][3] + matrix[i - 1][0];
}
cin >> printNum;
for(int i = 1; i < printNum + 1; i++)
{
cin >> result;
cout << i << " " << matrix[result][15] << endl;
}
return 0;
}
附:在别人的博客看到另外一种方法,操作起来更简单,但我看不懂(尤其是初始状态a0和b0为什么等于0)。能看懂的朋友,请给我讲解讲解。一下是他的博客http://blog.csdn.net/famousdt/article/details/7480103
最新文章
- QT操作EXCEL
- 基本排序算法——选择排序java实现
- 把Mongodb配置成windows服务
- 20145215《Java程序设计》第4周学习总结
- unity3d web.config设置
- sharedPreference的奇怪bug
- (三)backbone - API学习 - v0.9.2 与 v1.1.2区别
- kafka学习(四)-Topic &; Partition
- jquery表单序列化
- Linux入门篇(一)——文件
- 『开源重编译』System.Data.SQLite.dll 自适应 x86 x64 AnyCPU 重编译
- PHP获取日期时间信息
- 帮助类-从tfs获取数据
- 使用sqoop往hdfs中导入数据供hive使用
- Angular环境搭建
- 电信网关-天翼网关-GPON-HS8145C设置桥接路由拨号认证
- 总结)Nginx/LVS/HAProxy负载均衡软件的优缺点详解
- 解决DbContext对象创建问题
- 【Android开发日记】之入门篇(九)——Android四大组件之ContentProvider
- TransitionsTest