| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2269 人关注过本帖
标题:发一道题,大家帮忙想想
取消只看楼主 加入收藏
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
 问题点数:0 回复次数:7 
发一道题,大家帮忙想想
input 文件是类似于* * * * * * * *      *  
                  *            *     *   *
                  *           *    * *   * *
                  *            *
                  * * * * * * * *
这样的数个零碎地图形组成的数个文件,告诉了input文件的大小不会超过50乘以81,零碎的图形之间距离大于*和*之间的距离,同行同列*和*之间的距离是固定的
题目有几问,第一问是问图形是不是完整的,就是说,是不是一个矩形(当然这个只有在input是只有一个图形的情况下),这一问好做,就不多说了。
           第二问是问图形由几个零散图形组成
            
           第三问是问,所有图形有多少条边
           第四问是问,这些零散的图形能不能拼成一个矩形(大小未知)
我的做法是,把input文件放到50乘80的数组里,然后开始遍历,遇到星就把星变成#,然后在#的8个方向找,如果是*
就把星变成#,然后在下一个#8个方向找,直到把整个碎片变成#,同时在找的过程中,我会纪录方向,然后如果方向改变了,那么边++。然后开始重新遍历,找星,同样的方法把第二个图形变成#,然后图形个数++。
可是我实在不知道第四问怎么做,怎么判断能不能拼在一起呢?输出文件只要求回答能不能拼成矩形


请高手帮忙想想,谢谢了
搜索更多相关主题的帖子: input 
2008-09-08 05:20
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
没人顶,自己顶一下- -
2008-09-08 15:06
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
2楼的方法我想了一想,太耗费时间了吧?因为图形是不规则图形,而且,图形的边吻合的情况有很多的话,要重复验证多少次啊,而且题目的意思不是说两块或者3块,是要所有的拼在一起是矩形,嗯,还有,具体怎么实现呢,每次结合在一起,然后还要更新图形,判断是不是矩形的话岂不是还要重新计算每一次拼起来之后的顶点坐标,那样太复杂了吧。。。。
题目不是要求真去拼,只要求判断是不是能拼
今天问了一下老师,说了一个很重要的条件,就是这些碎片都是从一个完整矩形切的,只可能少某些块,所以我想用面积做,请大家指教下怎么计算不规则图形的面积,星号行距是2,列距是1,斜边是行列各加1。
2008-09-10 05:53
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
     
aa
阿谢谢楼上几位帮忙想,关于不规则图形计算,我想到了一个好方法,就是把不规则图形的顶点坐标记录下来,然后顺时针取点(逆时针也行,一个方向就行),绕图形一周,按照矢量算法,把所有边和坐标抽组成的梯形面积加起来(有正有负),就是不规则图形面积了,楼上的说到的星星个数的算法我也想过,可是在求和的时候总会出现一些差错,因为那种算法把没有把边当成理想边,就是说边也有厚度,但是图形组合拼起来的时候,边是合并的,所以会出现差错,只能把边当成无厚度的理想边才好算一些

另外关于矩形面积的计算,因为是英文版的题目,所以没看清楚意思。。。对不起大家了,后来发现了一个条件,就是不规则图形切割后不会乱摆,不会旋转,直角不会被切断,而且对于边来说,长和宽至少有一侧是只有两块不规则图形拼起来的,有了这两个条件,我根据直角边来计算矩形的长宽还是比较容易了

感谢大家的讨论,呵呵,我是新人,发现这个论坛很好很强大,我把题目贴在这里,如果你们有兴趣可以做一做,这是国外大学的assignment
2008-09-12 01:31
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
General description: Your program will read data from a data le that:
 contains at most 50 lines;
 contains at most 81 characters per line, including the ending new line character;
 contains only *s, simple spaces and new line characters.
If the name of the data le is data.txt then your program will be run as a.out <data.txt, so that
you will read the input as if it was coming from the keyboard. What is represented in the data le is
between 1 and 5 pieces of a possibly incomplete tile. The tile is fragmented if the number of pieces
is greater than 1. Four examples of data les are provided: data1.txt, data2.txt, data3.txt
and data4.txt.

Note that what has been represented above is the reconstructed tiles, not what is stored in the
data les, which you should examine while reading this.
Every piece is a polygon whose edges have four possible orientations. You can make the following
assumptions on what is represented in the data le (some assumptions are relevant to only some
of the questions).
 The tile has square corners and is not rotated (it has vertical and horizontal edges).
 The orientation of the pieces w.r.t. the tile is correct: the pieces are neither inverted nor
rotated.
 If pairs of consecutive *s on a common horizontal edge of a piece are stored in columns c1
and c2 , then jc1 􀀀 c2j = 2.
 If pairs of consecutive *s on a common vertical edge of a piece are stored in rows r1 and r2,
then jr1 􀀀 r2j = 1.
 If pairs of consecutive *s on a common diagonal edge of a piece are stored in rows r1 and r2
and in columns c1 and c2 , then jr1 􀀀 r2j = 1 and jc1 􀀀 c2j = 1.
 No piece contains any hole.

 Say that a * stored in row r1 and column c1 is a neighbouring * of a * stored in row r2 and
column c2 if either c1 = c2 and jr1 􀀀 r2j = 1, or r1 = r2 and jc1 􀀀 c2j = 2, or jr1 􀀀 r2j = 1
and jc1 􀀀 c2j = 1. The vertices of a given piece can be identi ed as those points marked
with a * from which it is possible to reach neighbouring *s in exactly two d erent directions
and in no opposite direction.


 Each corner of the tile is intact and preserved.

If a piece can match a corner of the tile, then that piece matches that corner of the tile.

Questions
Q1 Determine whether the tile in the data le is nonfragmented and complete. For this question,
the answer will be either
The tile is intact
or
The tile is not intact
If the tile is intact then no further output will be produced
Q2 Determine the total number of edges of all pieces. For this question, the answer will be of the
form
There is a total of ... edges
Q3 Determine the number of pieces, as well as the number of edges of the piece with the least
number of edges, and the number of edges of the piece with the greatest number of edges.
For this question, the answer will be of the form
There is a unique piece, having ... edges
or
There is a total of ... pieces, that all have ... edges
or
There is a total of ... pieces, that have between ... and ... edges
Q4 Determine whether the tile is complete. For this question, the answer will be either
The tile is complete
or
The tile is incomplete


Sample outputs
$ a.out <data1.txt
The tile is intact
$ a.out <data2.txt
The tile is not intact
There is a total of 7 edges
There is a unique piece, having 7 edges
The tile is incomplete
$ a.out <data3.txt
The tile is not intact
There is a total of 35 edges
There is a total of 4 pieces, that have between 7 and 11 edges
The tile is complete
$ a.out <data4.txt
The tile is not intact
There is a total of 43 edges
There is a total of 4 pieces, that have between 5 and 14 edges
The tile is incomplete
2008-09-12 01:53
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
关于几个条件,要用图形解释,我copy过来就变形状了。。。
我只好解释一下,其实也没太多条件了
几个重要的,一,如果一个图形能够符合矩形的一个角,那么这个图形就肯定是矩形的一个角
就是说,比如你找到一个这样的
*
  *
* * *
三角形,那么这个三角形肯定是矩形的左下角
二,上底或者下底,左边或者右边,必定有一个是只有两块碎片拼成的,也就是说,你能找到四个角,那把它们所在的边分别相加,得到的上底和下底,那个长一些那个就是矩形的底,同样,左边和右边。

三,横排的星间距是2,竖排的是1,斜的是坐标各加1

四,不会出现中间有孔的图形
2008-09-12 02:01
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
附件里是sample输入,可以看看,还是有很多需要考虑的地方的
ass2.rar (1.14 KB)
2008-09-12 02:05
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
发了题目之后发现没有反应就一直没有来。。。结果发现大家还是注意到了。。。

题目条件说了角不会被切开
还有顶点不会有3邻居(或以上)
还有直角都会被保留,
还有,如果长和宽至少一个是只有两块碎片就可以拼成了,

所以只要找到外部直角(注意:内部也有直角,看输入文件3),然后把直角边相加,上边和上边加,下边加下边,左右也是这样,然后比较长的就是拼成的矩形边了


所以题目就简化了很多

刚拿到手时觉得比较困难,仔细读题目了之后还是发现不难实现的

比较难的面积计算有人用海伦公式,不过我认为我之前说的矢量算法应该是最简单的了

我用数组做的,代码长度200多行
2008-09-21 18:16
快速回复:发一道题,大家帮忙想想
数据加载中...
 
   



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

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