| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 710 人关注过本帖
标题:USACO上的一道题
只看楼主 加入收藏
flylee
Rank: 5Rank: 5
等 级:职业侠客
帖 子:309
专家分:374
注 册:2004-8-10
收藏
 问题点数:0 回复次数:3 
USACO上的一道题

第一次做这种类型的题,大家帮忙看一下

Transformations

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

#1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
#2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
#3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
#4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
#5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
#6: No Change: The original pattern was not changed.
#7: Invalid Transformation: The new pattern was not obtained by any of the above methods.
In the case that more than one transform could have been used, choose the one with the minimum number above.

PROGRAM NAME: transform
INPUT FORMAT
Line 1: A single integer, N
Line 2..N+1: N lines of N characters (each either `@' or `-'); this is the square before transformation
Line N+2..2*N+1: N lines of N characters (each either `@' or `-'); this is the square after transformation

SAMPLE INPUT (file transform.in)
3
@-@
---
@@-
@-@
@--
--@

OUTPUT FORMAT
A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation.
SAMPLE OUTPUT (file transform.out)
1

搜索更多相关主题的帖子: USACO 
2006-08-28 14:31
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
汗,也不翻译一下,就把原题给搬来了.

汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-08-28 23:11
flylee
Rank: 5Rank: 5
等 级:职业侠客
帖 子:309
专家分:374
注 册:2004-8-10
收藏
得分:0 

题目大意就是,给定一个n*n的由黑色和白色方格组成的区域,要求出由初始状态到最终状态所用的最少的操作(操作可能不止一步)

可以使用的操作有:
1 顺时针旋转90度
2 顺时针旋转180度
3 顺时针旋转270度
4 以一条竖直的直线为对称轴水平翻转
5 水平翻转过后再结合1到3中的任一种旋转
6 不作改变
7 不能使初始状态经上述操作后变为终结状态

输入:
第1行:一个整数n(1<=n<=10)
第2行到第n+1行(转换前的状态):每行由n个字符组成(每个都是'@'或者'-')
第n+2行到第2*n+1行(转换后的状态):同上

输出:
独立的输出一行:1到7中的数字组成,表示经由这些数字代表的操作后,使初始状态转变为最终状态的最少操作


比如:
输入:

3
@-@
---
@@-
@-@
@--
--@

输出:

1

(初始状态顺时针旋转90度即得最终状态)

2006-08-29 16:50
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
楼主E文真好,
一些不成熟的想法:
这道题的可允许的操作真是多,但状态应该不会太多(没仔细想);
应该可以用双向广搜解决,从初始转态和目标状态同时扩展,结合好的哈希函数进行状态的判重(关键).

汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-08-29 17:27
快速回复:USACO上的一道题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019553 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved