搜索 此题数据小，不需要状压

Program P1856;
var
   n,m,i,j,ans:longint;
   c:char;
   f:array[0..1010,0..1010] of boolean;
function find(x,y:longint):boolean;
var
   i,j,k,l:longint;
begin
   i:=x;j:=y;
   while f[x,j] do inc(j);
   dec(j);
   while f[i,y] do inc(i);
   dec(i);
   for k:=x to i do
      for l:=y to j do
      begin
         if not(f[k,l]) then exit(false);
         f[k,l]:=false;

      end;
   for k:=x-1 to i+1 do
      if f[k,j+1] or f[k,y-1] then exit(false);
   for l:=y to j do
      if f[i+1,l] or f[x-1,l] then exit(false);




   exit(true);



end;
function main:boolean;
var
   i,j:longint;
begin
   ans:=0;
   for i:=1 to n do
      for j:=1 to m do
         if f[i,j] then
         begin
            if not(find(i,j)) then exit(false)
            else inc(ans);
         end;

   exit(true);
end;
begin
   while not seekeof do
   begin
      fillchar(f,sizeof(f),false);
      readln(n,m);
      if (n+m=0) then break;
      for i:=1 to n do
      begin
         for j:=1 to m do
         begin
            read(c);
            if c='#' then f[i,j]:=true;

         end;
         readln;
      end;

      if main then writeln('There are ',ans,' ships.')
      else writeln('Bad placement.');
   end;
end.