首页 > 代码库 > 7.14_D题
7.14_D题
D. BLOCKS
时间限制 1000 ms 内存限制 65536 KB
题目描述
给定一个
输入格式
有多组数据,EOF结束。
输出格式
每行对应一个answer
输入样例
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
6 8
.....#.#
##.....#
###...##
.......#
##.....#
#..#...#
输出样例
There are 5 ships.
So Sad
题目链接:http://code.bupt.edu.cn/problem/p/407/
寻找是否存在不合法的矩形,如果没有,输出矩形个数,
我比较笨的方法就是,用一个结构体存储矩形的左上点和右下点的坐标,遍历一边矩阵,遇到“#”便开始处理,记录下此时点的坐标(x,y)为矩形的起始点,然后在这一行中,向后寻找“#”,如果遇到“.”就停止,并记录此时的y值(y1),作为结束点的坐标,然后从坐标(x+1,y)开始处理如果在y到y1之间既存在“#”,又存在“.”,则说明这个矩阵不合法,否则继续扫描,直到下一行全是“.”。接下来,在判断每一行的起始点纵坐标之前一行和结束点纵坐标后一行是否有“#”,如果有,也是非法输入。每次处理一个“#”都要将它设置成“.”,防止下次继续扫到这个点。
一种比较有技巧的方法是这样的:如果这个矩形是非法的,那一定存在这样的、、、 这四种情况中的一种,如果存在,则是非法,如果不存在,则数其中矩形的个数,而数数也是有技巧,只要存在这样的结构,,那就一定存在一个矩形,只需要统计矩形的个数即可。
学长们讲的方法是这样的:也是利用结构体存储结构体信息,然后记录每一个联通块的最大长度和最大宽度,如果联通块的面积等于最大长度*最大宽度,那么存在一个矩形,否则不存在,跳出。也是比较简单。
第一种方法的AC代码:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。