Accept: 183 Submit: 465
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Cao Cao was hunted down by thousands of enemy soldiers when he escaped from Hua Rong Dao. Assuming Hua Rong Dao is a narrow aisle (one N*4 rectangle), while Cao Cao can be regarded as one 2*2 grid. Cross general can be regarded as one 1*2 grid.Vertical general can be regarded as one 2*1 grid. Soldiers can be regarded as one 1*1 grid. Now Hua Rong Dao is full of people, no grid is empty.
There is only one Cao Cao. The number of Cross general, vertical general, and soldier is not fixed. How many ways can all the people stand?
Input
There is a single integer T (T≤4) in the first line of the test data indicating that there are T test cases.
Then for each case, only one integer N (1≤N≤4) in a single line indicates the length of Hua Rong Dao.
Output
Sample Input
Sample Output
Hint
Here are 2 possible ways for the Hua Rong Dao 2*4.
题意:
给出 T,代表有 T 组数组,后给出 N(1 ~ 4)。代表有 N * 4 个格子,现有 4 种格子块去填充这 N * 4 个格子,而 CaoCao 是必须用的,但是只能用 1 个。问一共有多少种填充方式。
思路:
DFS。N 最大也只有4,所以不会超时。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int vis[5][5], sum; int n, way; void dfs(int x, int y, int ans) { if (ans == sum) { ++way; return; } if (vis[x][y]) { if (y + 1 <= 4) dfs(x, y + 1, ans); else if (x + 1 <= n) dfs(x + 1, 1, ans); } else { vis[x][y] = 2; dfs(1, 1, ans + 1); vis[x][y] = 0; if (y + 1 <= 4 && !vis[x][y + 1]) { vis[x][y] = vis[x][y + 1] = 3; dfs(1, 1, ans + 2); vis[x][y] = vis[x][y + 1] = 0; } if (x + 1 <= n && !vis[x + 1][y]) { vis[x][y] = vis[x + 1][y] = 4; dfs(1, 1, ans + 2); vis[x][y] = vis[x + 1][y] = 0; } } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); sum = 4 * n; way = 0; for (int i = 1; i <= n - 1; ++i) { for (int j = 1; j <= 3; ++j) { memset(vis, 0, sizeof(vis)); vis[i][j] = 1; vis[i][j + 1] = 1; vis[i + 1][j] = 1; vis[i + 1][j + 1] = 1; dfs(1, 1, 4); } } printf("%d\n", way); } return 0; }
相关推荐
华容道是老少皆知的益智游戏,利用java的JFrame写出的华容道。
娱乐资源,切勿用于商业用途。 求解算法的实现请参考我编写的《C语言求解华容道游戏最少步数》博客,建议一下:C语言是一种很好的锻炼思维的编程语言,如果想设计有界面的小游戏,可以试一下简单轻巧的html+css+js...
6.8k 用的图形界面编程 linux系统直接用java -jar命令打开
华容道源码,益智游戏,里面是设计的相当不错的算法
采用A*算法解决华容道问题,参考了网上的棋局编码思想,算法效率有较大的提高。请用netbeans打开项目
一个C++.net的华容道游戏, 相信很多朋友都玩过, 在此和大家分享游戏实现源码, 希望大家多多支持.
实验课做的一个华容道,界面美观,绝对可以运行,基于ARM3000平台
一个由.NET WindowsForm上开发的华容道游戏
java华容道游戏源码,学习之用,要求jdk1.5以上
Android 华容道游戏源代码,代码中附加了详细的注释,很好的android学习资料,很值得学习哦
华容道游戏,可以进行2D和3D两种模式,内有说明文档
《 Hua Rong Dao》是一款传统的中国游戏,您需要将最大的盒子(和其中的角色称为Caocao)移到底部中心才能通过游戏。 在这种情况下,我们使用C ++和SDL来实现它。
huarongdao 华容道游戏 huarongdaoc没有完成 huarongdaohtml5完成,用javascript实现 点击 开始游戏 可以开始 点击 解题 搜索当前局面最优解并在下面输出 如果需要调整局面,修改huarongdaohtml5/huarongdao.js中的...
HUARONGDAO_SOL
华容道求解过程sql语句集
资源包含文件:设计报告+源码 本程序的架构借鉴了Spring Boot的设计思想,将块的移动、块相关数据的记录与主界面的相关实现方法分开,便于分段开发,也便于程序的迭代更新。从配置文件读入一个数组,该数组共53个数...
Java 课本实验 华容道(简易版),该程序用Java语言编写 ,棋盘上有10个不一样大小的按钮,棋盘最下方有两个空着的小方格,代表曹操逃出的位置,可以实现通过鼠标或者键盘移动界面上的按钮,最终使曹操移动到棋盘最...
HUARONG102 HUARONG102 HUARONG102 HUARONG102 HUARONG102HUARONG102 HUARONG102
delphi 华容道游戏~~有兴趣的参考一下
我用j2me编写的索爱手机有游戏程序屏幕(128*160)