这道题应该一看~~基本思路就出来~~从左上角扫到右下角~~扫一个没更新过的连通块...就先与前面已经确定的比较...并且是翻成八种情况都来比较...若有符合的~~那么就确定这个连通块是前面哪个相同的...若无一符合~~就计数器++..发现新的连通块~~~但仔细想想...会好麻烦的感觉..
我是这么处理的 :
1.记录前面的连通块..我就是记录了连通块上的某点坐标..因为只要知道了一个坐标~~从这个坐标开始DFS一次就能还原出这个连通块...
2.从上一个思路出发..扫到新的连通块..要判断其是否经过各种旋转对称和前面某块相等..那么可以跟着前面通过一个坐标拓展出整个连通块的过程一起拓展...并且是按相应"相同"的方向..这样在拓展同时就能判断出两个块是不是相等..试想..若题目中只能完全相等才能说是一样(只有一种形态不翻转对称)..那不就是跟着前面拓展的路经同时在拓展当前...
3.但是题目给出了8种方向..其实也好办..先人工判断出这八种形态的移动相对应的情况..也就是我手工打的turn这个表...比如说在1形态里拓展时向上走一步相等于2形态向左走一步,3形态向下走一步,4形态向左走一步,5形态向上走一步,6形态向左走一步,7形态向下走一步,8形态向右走一步.....前面的个连通块可以都假设成住一个形态..以一种形态的方式拓展~~我都是确定成了1型态~~这样就按这8个情况跟着前面某个确定好的连通块一起拓展..就可以判断出所有的情况是否有相同的.
4.还有一点相当重要..同时拓展..除了相对方向要想同..更要起点相同...在记录前面连通块时我就是记录的连通块的最上面中最左边的点..而可以推出这个点在后面7个连通块中是在哪个位置...都是在连通块所有点的( MaxX or MinX , MaxY or MinY ) 上...人工判断下..所以我程序里写了那么长的判断更新...
这道题主要就是看着他给的第一个图...来推的...算法简单..但写起来繁琐...要求思路严谨..
Program:
分享到:
相关推荐
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2002年
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2001年
第1行: 3个用空格隔开的整数:N,P,以及K第2..P+1行: 第i+1行为3个用空格隔开的整数:A_i,B_i,L_i第1行: 输出1个整数,为FJ在这项工
第1行: 1个整数,N第2..N行: 每行为2个用空格隔开的整数A、B,为两块相邻草地的编号第1行: 输出1个整数,即FJ最少建立无线电通讯塔的数目输入说明:F
初始时,一个有N(5 ,000)枚硬币的堆栈放在地上,从堆顶数起的第I枚硬币的币值为C_i (1 ,000)。第1行
此C++程序是实现了USACO网站上的Magic Squares的问题。
Lineup 排队 USACO2007 (BZOJ1699 可提交) 6. BZOJ2738 矩阵乘法 7. BZOJ2311 花神游历各国 8. BZOJ1878 HH 的项链 9. BZOJ3132 上帝造题的七分钟 10. VIJOS1083 小白逛公园 图论 1. 货车运输 倍增 LCA+最小生成树 ...
我的USACO题解和程序
USACO1-5单元AC的代码~ 1 Chapter1 1.1 Section 1.1 1.2 Section 1.2 1.3 Section 1.3 1.4 Section 1.4 1.5 Section 1.5 2 Chapter2 2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 ...
与第 4 章衔接引入凸包,DP 的单调思想加强。Fencing the Cows 圈奶牛译 by Felicia Crazy描述农夫约翰想要建造一个围栏用来围住
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
这个是USACO题库中选出来的一些题,覆盖了多方面的知识点,利于锻炼C++学者的算法,里面还有部分题解
USACO chapter two.Useful for beginners.
USACO chapter one.May hope it useful to someone