- 浏览: 37818 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
原创文章转载请注明出处
摘要:枚举,棋盘翻转,位运算 , 三星
一. 题目翻译
1. 描述:
检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
2. 格式:
INPUT FORMAT:
(checker.in)
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
OUTPUT FORMAT:
(checker.out)
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
SAMPLE INPUT:
6
SAMPLE OUTPUT:
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
1. 题意理解(将问题分析清楚,大致用什么思路):
这道题目最基本的思路就是枚举,枚举所有可能出现的组合。
这里有三个限制的条件,也就是题目中的列限制、正对角线限制、反对角线限制。我们使用三个数组来表示,数组中元素为1表示当前的这个节点不可用。
但是即使是这样枚举,题目也很有可能超时。可以按照题目当中的hint做一个简单的优化:如果棋盘的大小N是偶数,则第一行只需要枚举前N/2列,这样没搜索出一种情况以后,沿中线翻转就可以产生另一个解(由于只枚举前N/2列所以不会重复)
要特别注意的是,这种算法在计算题目解的个数时可以减少复杂度。但是在N=6时,枚举第一行的前3列仅能产生2个解,所以需要对N=6的情况要进行单独的枚举。
2. 具体实现(具体实现过程中出现的问题):
参考代码注释。
3. 需要注意的细节:
棋盘大小N等于6的情况要单独考虑。
4. 启示:
翻转棋盘求解非常有意思,大家还可以思考更好的优化方法。
这道题目还有大神使用位运算,大家可以了解一下位运算。
三. 代码
/* ID:fightin1 LANG:JAVA TASK:checker */ //package session_1_5_4; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; import java.util.Scanner; public class checker { static int length; static int[] result; static int size; static int[] columnInUse; static int[] diagonalInUse1; static int[] diagonalInUse2; static PrintWriter pw; public static void main(String[] args) { try { // Scanner in = new Scanner(System.in); // pw = new PrintWriter(System.out); Scanner in = new Scanner(new BufferedReader(new FileReader( "checker.in"))); pw = new PrintWriter(new BufferedWriter(new FileWriter( "checker.out"))); length = in.nextInt(); size = 0; result = new int[length + 1]; columnInUse = new int[length + 1]; diagonalInUse1 = new int[2 * length + 1]; // "\" in use diagonalInUse2 = new int[2 * length + 1]; // "/" in use if (length == 6){ placeInRow(0); } else { if (length%2 == 0){ placeInRow(1); size = 2*size; } else { placeInRow(1); size = 2*size; columnInUse[length/2+1] = 1; diagonalInUse1[length/2 + length] = 1; diagonalInUse2[length/2 + 2] = 1; placeInRow(2); } } pw.println(size); pw.close(); in.close(); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } public static void placeInRow(int row){ if (row == length+1){ size ++ ; if (size<=3){ pw.print(result[1]); for (int i=2;i<=length;i++){ pw.print(" "+result[i]); } pw.println(); } } else { int bound = length; if (row == 0){ row = 1; } else if (row == 1){ bound = length/2; } for (int col = 1; col <= bound; col++){ int diagonal1 = col - row + length; int diagonal2 = col + row ; if(columnInUse[col]==0&&diagonalInUse1[diagonal1]==0&&diagonalInUse2[diagonal2]==0){ columnInUse[col] = 1; diagonalInUse1[diagonal1] = 1; diagonalInUse2[diagonal2] = 1; result[row] = col; placeInRow(row+1); columnInUse[col] = 0; diagonalInUse1[diagonal1] = 0; diagonalInUse2[diagonal2] = 0; result[row] = col; } } } } }
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 812原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 702原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1039原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 914原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 716原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 909原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 859原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 963原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 910原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 1005原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 720原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1306原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 870原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 746原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1011原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1043原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1214原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 660原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 697原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 892原创文章转载请注明出处 摘要:模拟 , 数学分析 ...
相关推荐
usaco_problem_files___1.1.1-1.5.4 就是usaco oj的部分问题集 方便有需要的人
著名online judging usaco的问题集,方便参加竞赛的同学
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作