Tyvj P1813 [JSOI2008]海战训练

P1813 [JSOI2008]海战训练
时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

为了准备高层峰会,元首命令武装部队必须处于高度戒备。警察将监视每一条大街,军队将保卫建筑物,领空将布满了JS-2008飞机。此外,巡洋船只和舰队将被派去保护海岸线。

但不幸的是因为种种原因,海军部仅有很少的几位军官能指挥大型海战。因此,他们考虑培养一些新的海军指挥官,为此选择了“海战”这一游戏来帮助训练。

在这个著名的游戏中,一个方形的盘上放置了固定数量和形状的船只,每只船却不能碰到其它的船。在这个题中,我们仅考虑船是方形的,所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。

输入格式

输入文件头一行由用空格隔开的两个整数R和C组成,1<=R,C<=1000,这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符,每个字符可以为“#”,也可为“.”,“#”表示船只的一部分,“.”表示水。

输出格式

为每一个段落输出一行解。如果船的位置放得正确(即棋盘上只存在相互之间不能接触的方形,如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只,则称这两艘船相互接触了)。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。

测试样例1

输入

6 8 
.....#.# 
##.....# 
##.....# 
.......# 
#......# 
#..#...#

输出

There are 5 ships.

备注

JSOI2008江苏省青少年信息学奥林匹克代表队组队选拔赛第二轮试题
 
题解:昨天刚刚学的悬线法求矩形居然今天就用到了——这个题里面需要求出每个点的左侧、右侧、上方、下方各有多少个“1”点(本程序中包含自己),然后接下来的任务就是判断矩形,我的做法如下——在表格中枚举每个左侧、上方均为0但是自身为1的点(一般也就是矩形的左上角),然后从此点一直向下,检测此点的左侧是否一直只有自己1个点,右侧宽度是否一直一致;然后从此点再向右扫,看上方是否一直只有自己1个点,下方高度是否保持一致。假如出现问题则说明出现了黏在一起的多个矩形,则Bad placement.(HansBug:则OrzPhile嘿嘿嘿。。。 Phile:TT);假如一切正常则正方形数+1,然后继续。。。(特别提醒:输出时别忘了格式是There are X ships.)
 
 1 var
 2    i,j,k,l,m,n,tt:longint;
 3    a,b,dow,up,lef,rig:array[0..1050,0..1050] of longint;
 4    c1:char;
 5 procedure OrzPhile;
 6           begin
 7                writeln(Bad placement.);
 8                halt;
 9           end;
10 begin
11      readln(n,m);
12      for i:=1 to n do
13          begin
14               for j:=1 to m do
15                   begin
16                        read(c1);
17                        case c1 of
18                             .:a[i,j]:=0;
19                             else a[i,j]:=1;
20                        end;
21                   end;
22               readln;
23          end;
24      fillchar(b,sizeof(b),0);
25      fillchar(dow,sizeof(dow),0);
26      fillchar(rig,sizeof(rig),0);
27      fillchar(lef,sizeof(lef),0);
28      for i:=1 to n do
29          for j:=1 to m do
30              begin
31                   if a[i,j]=1 then lef[i,j]:=lef[i,j-1]+1 else lef[i,j]:=0;
32                   if a[i,j]=1 then up[i,j]:=up[i-1,j]+1 else up[i,j]:=0;
33              end;
34      for i:=n downto 1 do
35          for j:=m downto 1 do
36              begin
37                   if a[i,j]=1 then rig[i,j]:=rig[i,j+1]+1 else rig[i,j]:=0;
38                   if a[i,j]=1 then dow[i,j]:=dow[i+1,j]+1 else dow[i,j]:=0;
39              end;
40      tt:=0;
41      for i:=1 to n do
42          for j:=1 to m do
43              if (a[i,j]=1) and (a[i-1,j]=0) and (a[i,j-1]=0) then
44                 begin
45                      for k:=1 to dow[i,j] do
46                          begin
47                               if lef[i+k-1,j]>1 then OrzPhile;
48                               if rig[i+k-1,j]<>rig[i,j] then OrzPhile;
49                          end;
50                      for k:=1 to rig[i,j] do
51                          begin
52                               if up[i,j+k-1]>1 then OrzPhile;
53                               if dow[i,j+k-1]<>dow[i,j] then OrzPhile;
54                          end;
55                      inc(tt);
56                 end;
57      writeln(There are ,tt, ships.);
58 end.
59                   

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。