呵呵，很水的一道题。
#include <iostream>
using namespace std;
int n,m,s;
char x[1001][1001];
int ship(int a,int b,int l1,int l2)
{
for (int i=b;i<=l2;i++)
if(x[a-1][i]=='#' || x[l1+1][i]=='#') return false;
for (int i=a;i<=l1;i++)
if(x[i][b-1]=='#' || x[i][l2+1]=='#') return false;
for (int i=a;i<=l1;i++)
for (int j=b;j<=l2;j++)
if(x[i][j]=='.') return false;
return true;
}
void draw(int a,int b)
{
x[a][b]='$';
if(x[a+1][b]=='#') draw(a+1,b);
if(x[a-1][b]=='#') draw(a-1,b);
if(x[a][b+1]=='#') draw(a,b+1);
if(x[a][b-1]=='#') draw(a,b-1);
}
int main()
{
cin >> n >> m;
for (int i=1;i<=n;i++) cin >> x[i];
for (int i=1;i<=n;i++)
{
for (int j=m;j>=1;j--)
x[i][j]=x[i][j-1];
x[i][0]='\0';
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if(x[i][j]=='#')
{
int l1=i,l2=j;
while(x[l1][j]=='#') l1++;
while(x[i][l2]=='#') l2++;
l1--;
l2--;
if(ship(i,j,l1,l2)==true)
{
draw(i,j);
s++;
}
else
{
cout << i << ' ' << j << ' ' << l1 << ' ' << l2 << endl;
cout << "Bad placement." << endl;
system("pause");
return 0;
}
}
}
cout << "There are " << s << " ships." << endl;
system("pause");
return 0;
}

点击查看程序源码+详细题解

var map:array[-10..1200]of ansistring;

i,s,r,c,x,y,x1,y1,ss:longint;

procedure find(i,j:longint);

begin

map:='.';

inc(ss);

if i>x1 then x1:=i;

if j>y1 then y1:=j;

if map='#' then find(i-1,j);

if map='#' then find(i,j-1);

if map='#' then find(i+1,j);

if map='#' then find(i,j+1);

end;

begin

readln(r,c);

for i:=1 to r do

begin readln(map[i]);

map[i]:='.'+map[i]+'.';

end;

for i:=1 to length(map[1])do map[0]:=map[0]+'.';

map[r+1]:=map[0];

for x:=1 to r do

for y:=1 to c+1 do

if map[x,y]='#' then

begin

x1:=x;

y1:=y;

ss:=0;

find(x,y);

if ss(x1-x+1)*(y1-y+1)

then begin

writeln('Bad placement.');

halt;

end;

inc(s);

end;

writeln('There are ',S,' ships.');

end.

数据弱爆了

4 4

....

.##.

##..

....

There are 1 ships.

错误

但是

竟然一次AC

#01: Accepted (171ms, 4508KB)

#02: Accepted (171ms, 4508KB)

#03: Accepted (222ms, 4508KB)

#04: Accepted (207ms, 4508KB)

#05: Accepted (226ms, 4508KB)

#06: Accepted (226ms, 4572KB)

#07: Accepted (210ms, 4508KB)

#08: Accepted (207ms, 4508KB)

#09: Accepted (195ms, 4508KB)

#10: Accepted (289ms, 4508KB)

Accepted / 100 / 2128ms / 4572KB

为何不能秒杀？？？？？？？

├ 测试数据 01：答案错误...

　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案正确... 0ms 

├ 测试数据 03：答案正确... 0ms 

├ 测试数据 04：答案正确... 0ms 

├ 测试数据 05：答案正确... 0ms 

├ 测试数据 06：答案正确... 0ms 

├ 测试数据 07：答案正确... 0ms 

├ 测试数据 08：答案正确... 0ms 

├ 测试数据 09：答案正确... 0ms 

├ 测试数据 10：答案正确... 0ms 

这是一个坑爹的题目...

原来只要有一个不是矩形就要输出‘Bad placement.'

害我交了n次!!

不用递归也可以0msAC

另外，那几个句号真害人

...

郁闷，There are S ships.”,忘了加那个点，交了N次都没过

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

30题纪念

参照以前的DFS写了个结果发现DFS变量里的边界条件错误...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

传说我把p打成大写的了没有一次ac

- -|||

我确定

只有第10个点超过了300

强烈鄙视无解条件。。走人。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 244ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

竟然是在第6个点上耗时间……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

晕,第一次看错数据范围,数组只开100*100,

结果最后一点就TLE,开成1000*1000

就0ms...

唉,rp不行哪...

我用的"送给圣诞夜的极光"源程序交的,改了2句话...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

var

a:array[1..1001,1..1001]of boolean;

s:char;

r,c,i,j,k:longint;

procedure dfs(i,j:longint);

begin

a:=false;

if a then dfs(i,j+1);

if a then dfs(i,j-1);

if a then dfs(i+1,j);

if a then dfs(i-1,j);

end;

begin

readln(r,c); k:=0;

for i:=1 to r do

begin

for j:=1 to c do

begin

read(s);

if s='#'then a:=true;

end;

readln;

end;

for i:=1 to r-1 do

for j:=1 to c-1 do

if (a and aand aand not(a))or

(a and aand aand not(a))or

(a and aand aand not(a))or

(a and aand aand not(a))

then begin writeln('Bad placement.');halt;end;

for i:=1 to r do

for j:=1 to c do

if athen begin inc(k);dfs(i,j);end;

writeln('There are ',k,' ships.');

end.

楼下鉴别'Bad placement.'的方法很巧妙，借鉴了一下。不过这种判断方法浪费2倍时间。有没有什么更好巧妙的方法但是也要好写？

program p1076;

var a:array[0..1001,0..1001] of char;

i,j,k,l,m,n,q,w,e,s,d,r,c,z,x,banzhuansb:longint;

procedure f(x,y:longint);

begin

a[x,y]:='.';

if a[x,y+1]='#' then f(x,y+1);

if a[x,y-1]='#' then f(x,y-1);

if a[x+1,y]='#' then f(x+1,y);

if a[x-1,y]='#' then f(x-1,y);

end;

begin

readln(r,c);

for i:=1 to r do begin

for j:=1 to c do

read(a); readln; end;

for i:=1 to r do

for j:=1 to c do

if ((a='#') and (a='#') and (a='#') and (a='.'))

or ((a='#') and (a='.') and (a='#') and (a='#'))

or ((a='#') and (a='#') and (a='.') and (a='#'))

or ((a='.') and (a='#') and (a='#') and (a='#'))

then

begin

writeln('Bad placement.');

halt;

end;

for i:=1 to r do

for j:=1 to c do

if a='#' then begin f(i,j); inc(banzhuansb); end;

writeln('There are ',banzhuansb,' ships.');

end.

沉船。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms