我用的是减法思路，就是每扫到一个“#”，就找与之相连的所有“#”（也就是找到这个“#”块），然后记录这个“#”块的上下左右界，如果是合法的船，那么这个船的面积就一定是（右界-左界+1）乘（下界-上界+1），如果不是合法的船，它的面积一定小于这个值。我们在输入时记录“#”总数js，然后不断用js减去这些面积。如果最后js=0，说明整张图船的摆放是合法的，那么直接输出船的数量ans，否则摆放是不合法的，输出bad pacement。

#include<iostream>
#define INF 0x3f3f3f3f; 
using namespace std;
int n,m,zj,yj,sj,xj,js,ans;
int a[1005][1005];
char b;
void update()
{
    zj=INF;
    yj=-INF;
    sj=INF;
    xj=-INF;
} 
int cover(int s,int t)
{
    if(t<zj)
    zj=t;
    if(t>yj)
    yj=t;
    if(s<sj)
    sj=s;
    if(s>xj)
    xj=s;
    a[s][t]=0;
    for(int i=s-1;i<=s+1;++i)
    {
        for(int j=t-1;j<=t+1;++j)
        {
            if(a[i][j]==1)
            cover(i,j);
        }
    }
    return zj,yj,sj,xj;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>b;
            if(b=='.')
            a[i][j]=0;
            else
            {
                a[i][j]=1;
                js++;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]==1)
            {
                ans++;
                update();
                cover(i,j);
                js-=(yj-zj+1)*(xj-sj+1); 
            } 
        }
    }
    if(js==0)
    cout<<"There are "<<ans<<" ships.";
    else
    cout<<"Bad placement.";
    return 0;
 } 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
bool map[1001][1001];
int sum[1001][1001];
char cc;
int n,m,k = 1,ans;

int check(int x,int y) {
    int i = x,j = y,num=1;
    map[i][j] = 0;
    sum[i][j] = k;
    while( map[i][j-1] == 1 && j-1 > 0 ) {
        j--;
        map[i][j] = 0;
        sum[i][j] = k;
        num ++;
    }
    i = x;j = y;
    while (map[i][j+1] == 1 && j+1 <= m) {
        j ++;
        map[i][j] = 0;
        sum[i][j] = k;
        num++;
    }
    return num;
}

bool find(int x,int y) {
    int i = x,j = y,num = 1;
    do {
        if (map[i+1][j] == 1 && i+1 <= n)
            i++;
        if (map[i][j+1] == 1 && j+1 <= m)
            j++;
    }while (map[i+1][j] == 1 || map[i][j+1] == 1);
    //cout<<i<<" "<<j<<endl;    
    map[i][j] = 0;
    sum[i][j] = k;
    //while ( map[i+1][j] == 1 && i+1 <= n) i++;
    //while ( map[i][j+1] == 1 && j+1 <= m) j++;
    while (map[i][j-1] == 1) {
        j--;
        num++;
        if (map[i+1][j] == 1) return 0;
        map[i][j] = 0;
        sum[i][j] = k;
    }
    j = y;
    while (map[i-1][j] == 1) {
        i--;
        int ch= check(i,j);
        if (num != ch) 
            return 0;
    }
    return 1;
}
int main() {
    //freopen("BATTLE.in","r",stdin);
        //freopen("BATTLE.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            cin>>cc;
            if ( cc != '#') map[i][j] = 0;
            else map[i][j] = 1;
        }
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++)
            if (map[i][j] == 1 ) {
                if ( !find(i,j) ) {
                    cout<<"Bad placement."<<endl;
                    return 0;
                }
                else k++;
            }
    printf("There are %d ships.\n",k-1);
    return 0;
}

写的好丑啊~~~~QAQ

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1480 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1488 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1484 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1484 KiB, score = 10
Accepted, time = 30 ms, mem = 1488 KiB, score = 100
代码
#include <bits/stdc++.h>
const int max_rc = 1001;
char map[max_rc][max_rc];
int r,c;
bool flag;
int count,l = 1;
int main() {
  scanf("%d %d\n",&r,&c);
  memset(map,'\0',sizeof(map));
  for (int i = 1;i <= r;i++)
    scanf("%s\n",&map[i][1]);
  for (int i = 1;i <= r;i++)
    for (int j = 1;j <= c;j++)
      if (map[i][j] == '#') {
        map[i][j] = '0';
        for (int k = j;k <= c;k++) {
          if (map[i][k] == '.') break;
          else {
            map[i][k] = '0';
            count = k;
          }
        }
        flag = true;
        for (int k = i;k <= r;k++) {
          for (int f = j;f <= count;f++)
            if (map[k][f] == '#') map[k][f] = '0';
          for (int f = j;f <= count;f++)
            if (map[k][f] != '0') {
              flag = false;
              for (int y = j;y <= count;y++)
                if(map[k][y]=='0')map[k][y]='#';
              break;
            }
          if (!flag) break;
        }
        for (int k = 1;k <= r;k++)
          for (int f = 1;f <= c;f++)
            if (map[k][f] == '0') map[k][f] = l+'0';
        l++;
    }
  flag = true;
  for (int i = 1;i <= r;i++) {
    for (int j = 1;j <= c;j++)
      if (map[i][j] != '.') {
        if (map[i+1][j] != '.' && map[i+1][j] != '\0' && map[i+1][j] != map[i][j]) {
          flag = false;
          break;
        }
        if (map[i-1][j] != '.' && map[i-1][j] != '\0' && map[i-1][j] != map[i][j]) {
          flag = false;
          break;
        }
        if (map[i][j+1] != '.' && map[i][j+1] != '\0' && map[i][j+1] != map[i][j]) {
          flag = false;
          break;
        }
        if (map[i][j-1] != '.' && map[i][j-1] != '\0' && map[i][j-1] != map[i][j]) {
          flag = false;
          break;
        }
      }
    if (!flag) break;
  }
  if (flag) printf("There are %d ships.",l - 1);
  else printf("Bad placement.");
  return 0;
}

其实对于每一个可能符合要求的船只进行宽的记录然后向下扫就可以了

#include<iostream>
#include<cstdio>
using namespace std;
char juz[1005][1005];
int juzz[1005][1005],n,m,mark;
bool pd;
void dfs(int x,int y)
{
    int i,j,wide=0,jil=0;
    for(i=y;;i++)
    {
        if(juzz[x][i+1])
        {
        pd=1;
        break;
        }
        if(juz[x][i]=='.' || i>m)
        break;
        wide++;//记录宽度
    }
    for(j=x;;j++)
    {
        for(i=0;i<=wide;i++)
        {
            if(juz[j][y+i]=='#')
            jil++;
        }
        if(jil==wide || jil==0)
        {
            if(jil==wide)      //宽度符合记录那就进行覆盖（剪枝）
            for(i=0;i<wide;i++)
            juzz[j][y+i]=mark;
            if(jil==0)  //如果根本没有任何可能成为船只的部分就跳出
            break;
        }
        else//下方存在宽度但并不满足记录的宽度说明两艘船相撞了
        {
            pd=1;
            break;
            
        }
        jil=0;
        
    }
}
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>juz[i][j];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(juzz[i][j]==0 && juz[i][j]=='#')
            {
                mark++;
                dfs(i,j);
            }
            if(pd)
            {
                cout<<"Bad placement.";
                return 0;
            }
            
        }
    }
    cout<<"There are "<<mark<<" ships.";
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,x_min=100000,x_max=-1,y_min=100000,y_max=-1;
int xku[5]={0,1,-1,0,0},yku[5]={0,0,0,1,-1};
char a[1010][1010]={0};
bool b[1010][1010]={0};
bool check(int x,int y)
{
    if(x<=0||y<=0||x>n||y>m||!b[x][y]||a[x][y]=='.')
        return false;
    return true;
}
void bfs(int x,int y)
{
    b[x][y]=false;
    if(x_min>x)
        x_min=x;
    if(y_min>y)
        y_min=y;
    if(x_max<x)
        x_max=x;
    if(y_max<y)
        y_max=y;
    for(int i=1;i<=4;i++)
    {
        if(check(x+xku[i],y+yku[i]))
        {
            bfs(x+xku[i],y+yku[i]);
        }
    }
}
int main()
{
    int i,j,num=0,e=0;
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%c",&a[i][j]);
            if(a[i][j]=='#')
                b[i][j]=true;
        }
        getchar();
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='#'&&b[i][j])
            {
                num++;
                bfs(i,j);
                for(int q=x_min;q<=x_max;q++)
                {
                    for(int w=y_min;w<=y_max;w++)
                    {
                        if(a[q][w]=='.')
                        {
                            e=1;
                            break;
                        }
                        else
                            a[q][w]='.';
                    }
                    if(e)
                        break;
                }
                if(e)
                {
                    printf("Bad placement.\n");
                    return 0;
                }
                x_min=100000,x_max=-1,y_min=100000,y_max=-1;
            }
        }
    }
    printf("There are %d ships.",num);
    return 0;
}

/*
bfs,添加v数组判重减少搜索量，51、52行为核心判断语句，
判断是否有船挨在一起，即是否能构成一个规则方形，若不能直接输出；
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

struct node
{
    int x,y;
    node(int x,int y):x(x),y(y){}
};
int n,m;
int v[1002][1002];
int a[1002][1002];
int ans,bad;
int xy[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
queue<node> q;

void bfs(int x,int y)
{
    int tot=0;
    node e(x,y);
    v[x][y]=1;
    q.push(e);
    int x1=x,x2=x,y1=y,y2=y;
    while(!q.empty())
    {
        node r=q.front();
        q.pop();
        tot++;
        for(int i=0;i<4;i++)
        {
            int zx=r.x+xy[i][0];
            int zy=r.y+xy[i][1];
            if(a[zx][zy]&&!v[zx][zy]&&zx<=n&&zx>=1&&zy<=m&&zy>=1)
            {
                node p(zx,zy);
                v[zx][zy]=1;
                q.push(p);
                x1=max(x1,zx);  x2=min(x2,zx);
                y1=max(y1,zy);  y2=min(y2,zy);
            }
        }
    }
    if((x1-x2+1)*(y1-y2+1)!=tot)
        bad=1;
}

int main()
{
    char ch;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='#')
                a[i][j]=1;
        }   
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        if(!v[i][j]&&a[i][j])
        {
            ans++;
            bfs(i,j);
            if(bad)
            {
                cout<<"Bad placement."<<endl;
                return 0;
            }
        }
    }
    cout<<"There are "<<ans<<" ships."<<endl;
    return 0;
}
     

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
char Map[1005][1005];
int temp[1005][1005];

void dfs(int x, int y, int id) {
if (x < 1 || x > n || y < 1 || y > m) return ;
if (temp[x][y] != 0 || Map[x][y] != '#') return ;
temp[x][y]=id;
dfs(x+1, y, id);
dfs(x, y+1, id);
dfs(x-1, y, id);
dfs(x, y-1, id);

}

int main() {
ios::sync_with_stdio(false);

cin >> n >> m;
for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
cin >> Map[i][j];
}
}

memset(temp, 0, sizeof(temp));
int t=0;

for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
if (temp[i][j] == 0 && Map[i][j] == '#') dfs(i, j, ++t);
}
}

for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
int pd=0;
if (temp[i][j] != 0) pd++;

if (temp[i-1][j] != 0) pd++;
if (temp[i][j-1] != 0) pd++;
if (temp[i-1][j-1] != 0) pd++;
if (pd == 3) t=0;

}
}

if (t == 0) cout << "Bad placement.";
else cout << "There are " << t << " ships.";

return 0;
}

我去，真心要审题啊，只要不是矩形就属于相互接触，就直接输出“Bad placement.”

#include<iostream>
#include<cstring>
#include<cstdio>
#include <string>

const int maxn = 2000;


using namespace std;
char a[maxn][maxn], a1[maxn][maxn];
int count, sx, sy, ex, ey;

void DFS(int r, int c){
    a[r][c] = '.';

    ex = max(ex, r); ey = max(ey, c);
    sx = min(sx, r); sy = min(sy, c);
    
    if (a[r+1][c] == '#') DFS(r+1, c);
    if (a[r][c+1] == '#') DFS(r, c+1);
    if (a[r-1][c] == '#') DFS(r-1, c);
    if (a[r][c-1] == '#') DFS(r, c-1);
    
}
int main(){
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i <= n+1; i++)
        for (int j = 0; j <= m+1; j++)
            a[i][j]='.';
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin>>a[i][j];
    
    memcpy(a1, a, sizeof(a));
    
    for (int mm = 1; mm <= n; mm++)
        for (int jj = 1; jj <= m; jj++)
            if (a[mm][jj] == '#') {
                
                count++;
                sx = n; sy = m;
                ex = ey = 1;
                DFS(mm, jj);
                
                for (int i = sx; i <= ex; i++)
                    for (int j = sy; j <= ey; j++)
                        if (a1[i][j] != '#') {
                            cout<<"Bad placement.";
                            return 0;
                        }
                
            }
    cout<<"There are "<<count<<" ships.";
    return 0;
}

const
dx:array[1..4]of shortint=(0,1,-1,0);
dy:array[1..4]of shortint=(1,0,0,-1);

var
n,total,ss,m,i,j,maxx,maxy,minx,miny:longint;
map:array[1..1000,1..1000]of boolean;
ch:char;

procedure find(x,y:longint);
var
xx,yy,nx,ny,i,j,t,w:longint;
h:array[1..1000010,1..2]of longint;

begin
if not(map[x,y]) then exit;
inc(total);map[x,y]:=false;
h[1,1]:=x;h[1,2]:=y;
t:=1;w:=1;ss:=1;maxx:=x;maxy:=y;minx:=x;miny:=y;

while t<=w do
begin
for i:=1 to 4 do
begin
nx:=h[t,1]+dx[i];ny:=h[t,2]+dy[i];
if (nx<=n)and(nx>=1)and(ny<=m)and(ny>=1)and(map[nx,ny])
then
begin
inc(w);h[w,1]:=nx;h[w,2]:=ny;map[nx,ny]:=false;
inc(ss);

if nx>maxx then maxx:=nx;
if ny>maxy then maxy:=ny;
if nx<minx then minx:=nx;
if ny<miny then miny:=ny;
end;
end;
inc(t);
end;
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
if ch='.' then map[i,j]:=false;
if ch='#' then map[i,j]:=true;
end;
readln;
end;
for i:=1 to n do
for j:=1 to m do
begin
ss:=0;
if map[i,j] then
begin
find(i,j);
if abs(maxx-minx+1)*abs(maxy-miny+1)<>ss then
begin writeln('Bad placement.');halt;end;
end;
end;
writeln('There are ',total,' ships.');
end.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
struct node
{
int x,y;
}que[1100000];
int n,m,list[1100],head,tail,map[1100][1100],ans;
bool visit[110][110],bad=0;
char str[2100];
void bfs(int x,int y)
{
int ulx=x,uly=y,drx=x,dry=y;
head=tail=1;
que[1].x=x,que[1].y=y,visit[x][y]=1;
while(head<=tail)
{
node now=que[head++];
node next;
for(int i=0;i<4;i++)
{
next=now;
next.x+=dx[i],next.y+=dy[i];
if(next.x>=1 && next.x<=n && next.x>=1 && next.y<=m && !visit[next.x][next.y] && map[next.x][next.y])
{
visit[next.x][next.y]=1;
que[++tail]=next;
ulx=min(ulx,next.x);uly=min(uly,next.y);
drx=max(drx,next.x);dry=max(dry,next.y);
}

}
}
if((drx-ulx+1)*(dry-uly+1) != tail) bad = 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int j=1;j<=m;j++)
{
if(str[j]=='#')
map[i][j]=1;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!visit[i][j] && map[i][j])
{
ans++;
bfs(i,j);
if(bad==1)
{
printf("Bad placement.\n");
return 0;
}
}
printf("There are %d ships.\n",ans);
return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
struct node
{
int x,y;

}que[110000];
int head,tail,n,m;
bool bad=0;
int v[1100][1100];
int map[1100][1100];
char st[110];
void bfs(int x,int y)
{
int ulx=x,uly=y,drx=x,dry=y;
head=tail=1;
que[1].x=x;que[1].y=y;v[x][y]=1;
while(head<=tail)
{
node now=que[head++];
node next;
for(int i=0;i<4;i++)
{
next=now;
next.x+=dx[i];next.y+=dy[i];
if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m&&!v[next.x][next.y]&&map[next.x][next.y])
{
v[next.x][next.y]=1;
que[++tail]=next;
ulx=min(ulx,next.x);uly=min(uly,next.y);
drx=max(drx,next.x);dry=max(dry,next.y);
}
}
}
if((drx-ulx+1)*(dry-uly+1)!=tail)bad=1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
for(int j=1;j<=m;j++)
{
if(st[j]=='#')map[i][j]=1;
}
}
int ans=0;
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[i][j]==0&&map[i][j])
{
ans++;
bfs(i,j);
if(bad==1)
{
printf("Bad placement.");
return 0;
}

}
}
}
printf("There are %d ships.",ans);
return 0;
}

0.0无语要Bfs老师老师说要Bfs枚举秒过0.0

记录信息
评测状态 Accepted
题目 P1076 海战
递交时间 2015-08-04 21:24:34
代码语言 C++
评测机 VijosEx
消耗时间 80 ms
消耗内存 2908 KiB
评测时间 2015-08-04 21:24:35
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2900 KiB, score = 10
测试数据 #1: Accepted, time = 5 ms, mem = 2908 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2904 KiB, score = 10
测试数据 #3: Accepted, time = 1 ms, mem = 2904 KiB, score = 10
测试数据 #4: Accepted, time = 2 ms, mem = 2904 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2908 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2904 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2904 KiB, score = 10
测试数据 #9: Accepted, time = 42 ms, mem = 2900 KiB, score = 10
Accepted, time = 80 ms, mem = 2908 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
char map[1010][1010];
bool been[1010][1010];
int queue[50010][2];
int go[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int k=1,m,n;
void search(int x,int y)
{
int x1=x,x2=x,y1=y,y2=y;
int nowans=1;
int front=1;
int back=2;
been[x][y]=1;
queue[front][0]=x;
queue[front][1]=y;
for(;front<back;)
{
int nowx=queue[front][0];
int nowy=queue[front][1];
for(int i=0;i<=3;i++)
{
int gox=nowx+go[i][0];
int goy=nowy+go[i][1];
if(gox>=0&&gox<m&&goy>=0&&goy<n&&map[gox][goy]=='#'&&!been[gox][goy])
{
nowans++;
queue[back][0]=gox;
queue[back++][1]=goy;
been[gox][goy]=true;
x1=min(x1,gox);
x2=max(x2,gox);
y1=min(y1,goy);
y2=max(y2,goy);
}
}front++;
}
if((x2-x1+1)*(y2-y1+1)>nowans)
{
printf("Bad placement.");
k=0;
return;
}
}
int main()
{
int ans=0;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++)
scanf("%s",map[i]);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(map[i][j]=='#'&&!been[i][j])
{
ans++;
search(i,j);
if(!k)return 0;
}
}
printf("There are %d ships.",ans);
}

AC了

var
a:array[0..1000,0..1000] of char;
i,j,k,l,m,n,q,w,e,r,s,d,z,x,c:longint;
procedure f(q,w:longint);
begin
a[q,w]:='.';
if a[q+1,w]='#' then f(q+1,w);
if a[q-1,w]='#' then f(q-1,w);
if a[q,w+1]='#' then f(q,w+1);
if a[q,w-1]='#' then f(q,w-1);
end;
begin
readln(r,c);
for i:=1 to r do
begin
for j:=1 to c do read(a[i,j]);
readln;
end;
for i:=1 to r do
for j:=1 to c do
if ((a[i,j]='#') and (a[i+1,j]='#') and (a[i,j+1]='#') and (a[i+1,j+1]='.'))
or ((a[i,j]='#') and (a[i+1,j]='.') and (a[i,j+1]='#') and (a[i+1,j+1]='#'))
or ((a[i,j]='#') and (a[i+1,j]='#') and (a[i,j+1]='.') and (a[i+1,j+1]='#'))
or ((a[i,j]='.') and (a[i+1,j]='#') and (a[i,j+1]='#') and (a[i+1,j+1]='#'))
then
begin
writeln('Bad placement.');
halt;
end;
for i:=1 to r do
for j:=1 to c do
if a[i,j]='#' then
begin
f(i,j);
s:=s+1;
end;
writeln('There are ',s,' ships.');
end.

package vijosWrong;

import java.util.Scanner;

public class P1076 {
static int n,m,s,y0,y1,x1,x0;
static String a[];
static boolean b[][];

public static void input(){
Scanner in =new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
a = new String[n];
b = new boolean[n][m];
for (int i = 0;i<n;i++)
a[i] = in.next();
for (int i = 0;i<n;i++)
for (int j=0;j<m;j++)
b[i][j] = true;
}

public static void trys(int x, int y){
s++;
b[x][y] = false;
if (x<x0) x0 = x;
if (y<y0) y0 = y;
if (x>x1) x1 = x;
if (y>y1) y1 = y;

if (x+1<n)
if (b[x+1][y] && a[x+1].charAt(y) == '#')
trys(x+1,y);
if (y+1<m)
if (b[x][y+1] && a[x].charAt(y+1) == '#')
trys(x,y+1);
if (x-1>=0)
if (b[x-1][y] && a[x-1].charAt(y) == '#')
trys(x-1,y);
if (y-1>=0)
if (b[x][y-1] && a[x].charAt(y-1) == '#')
trys(x,y-1);

}

public static void main(String[] args) {

input();
int sum = 0;
for (int i = 0;i<n;i++)
for (int j = 0;j<m;j++)

if (a[i].charAt(j)=='#' && b[i][j]){
s = 0;
x0 = 10000;
y0 = 10000;
y1 = -1;
x1 = -1;
trys(i,j);
if ((y1-y0+1)*(x1-x0+1)==s)
sum++;
else {
System.out.println("Bad placement.");
System.exit(0);
}

}
System.out.println("There are "+sum+" ships.");
}
}
第五个点错了，求解！！！！

#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
bool map[1002][1002];
int line, column;
int ans=0;
bool go(){
int x, y,i,j;
for (x = 1; x <= line; x++){
for (y = 1; y <= column; y++){
if (map[x][y]){
ans++;
int ymax;
for (j = y; map[x][j]; j++);
ymax = j;
for (i = x; map[i][y]; i++){
if (map[i][y - 1])return false;
for (j = y; map[i][j]; j++){
if (!map[i][j])break;
map[i][j] = false;
}
if (j != ymax)return false;
}
}
}
}
}
int main(){
freopen("in.txt", "r", stdin);

cin >> line >> column;
char c;
int i, j;
memset(map, 0, sizeof(map));
for (i = 1; i <= line; i++){
for (j = 1; j <= column; j++){
cin >> c;
if (c == '#')
map[i][j] = true;
}
}
if (go())printf("There are %d ships.\n", ans);
else cout << "Bad placement." << endl;
return 0;
}

忘了这个dfs怎么写。。。。。。果断模拟
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 8376 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8376 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8376 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 8380 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 8380 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 8380 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 8380 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 8380 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 8376 KiB, score = 10
测试数据 #9: Accepted, time = 250 ms, mem = 8376 KiB, score = 10
Accepted, time = 280 ms, mem = 8380 KiB, score = 100
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1005;
char k[maxn][maxn]={0},vis[maxn][maxn]={0};
int numh,numl,numk=0;
int main()
{
scanf("%d%d",&numh,&numl);
for(int i=1;i<=numh;i++)
{

scanf("\n");
for(int j=1;j<=numl;j++)
scanf("%c",&k[i][j]);

}
for(int i=1;i<=numh;i++)
for(int j=1;j<=numl;j++)
if(!vis[i][j]&&k[i][j]=='#')
{
int m;
for(m=j;m<=numl;m++){if(k[i][m]=='#')vis[i][j]=1;else {m--;break;}}
if(m>numl)m=numl;
int l;
for(l=i+1;l<=numh;l++)
{ int c=0;
for(int n=j;n<=m;n++)
if(k[l][n]=='#'){c++;vis[l][n]=1;}
if(c>0&&c!=m+1-j){printf("Bad placement.\n");exit(0);}
if(!c)break;
}
for(int n=i;n<=l-1;n++){if(k[n][j-1]=='#'||k[n][m+1]=='#'){printf("Bad placement.\n");exit(0);}}
j=m;numk++;
}printf("There are %d ships.\n",numk);
return 0;
}

呃……居然Bad placement后面还有个句点！！！我晕……
对每一个点扫一遍就好了= = O(rc)的复杂度10^6妥妥的
对于每个点判断下，如果以它为右下角的2*2小正方形是有三个点是摆了船的，则是错误摆法
如果它左边和上边的点都没摆船而当前这个点摆了，则答案加一
so easy~

//Vijos 1076
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define rep(i,n) for(int i=1;i<=n;++i)
using namespace std;

int r,c,m[1000];
//bitset<1000>b[1000];
bool b[1001][1001];

int main()
{
// freopen("file.in","r",stdin);
// freopen("file.out","w",stdout);
scanf("%d%d",&r,&c);
char ch;
rep(i,r)
rep(j,c){
ch=getchar();
if (ch=='\n') ch=getchar();
if (ch=='#') b[i][j]=1;
else b[i][j]=0;
}
/*
for(int i=0;i<=r;++i){
for(int j=0;j<=c;++j)
cout <<b[i][j];
cout <<endl;
}*/
int ans=0;
rep(i,r)
rep(j,c){
bool x1=b[i-1][j-1],x2=b[i-1][j],y1=b[i][j-1],y2=b[i][j];
if (((x1^x2)&&(y1&y2))||((x1&x2)&&(y1^y2))){printf("Bad placement.\n");return 0;}
if (!b[i-1][j] &&b[i][j] &&!b[i][j-1]) ans++;
// printf("(%d,%d) ans=%d\n",i,j,ans);
}
printf("There are %d ships.\n",ans);
return 0;
}

P1076海战
Accepted

记录信息

评测状态 Accepted
题目 P1076 海战
递交时间 2014-10-31 21:37:56
代码语言 C++
评测机 Jtwd2
消耗时间 76 ms
消耗内存 2656 KiB
评测时间 2014-10-31 21:37:59

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2480 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 2476 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 2476 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2476 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 2476 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 2656 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 2476 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 2476 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 2476 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 2476 KiB, score = 10

Accepted, time = 76 ms, mem = 2656 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>

using namespace std;

int r , c;
int i , j;
int x , y;
char map[1000 + 2][1000 + 2];
bool f[1000 + 2][1000 + 2];
int ans;
int found;
int posx , posy;
int ptrx , ptry;

void dfs( int i , int j )
{
if( i < 0 || j < 0 )
return;
if( i >= r || j >= c )
return;
if( map[i][j] == '#' )
{
found = 1;
posx = min( posx , i );
posy = min( posy , j );
ptrx = max( ptrx , i );
ptry = max( ptry , j );
f[i][j] = 1;
map[i][j] = '.';
dfs( i - 1 , j );
dfs( i + 1 , j );
dfs( i , j - 1 );
dfs( i , j + 1 );

}
return;
}

int main()
{
while( scanf( "%d %d" , &r , &c ) != EOF )
{
ans = 0;
memset( f , 0 , sizeof( f ) );
for( i = 0 ; i < r ; i++ )
scanf( "%s" , map[i] );
for( i = 0 ; i < r ; i++ )
{
for( j = 0 ; j < c ; j++ )
{
posx = posy = 100000;
ptrx = ptry = 0;
found = 0;
dfs( i , j );
if( found )
{
for( x = posx ; x <= ptrx ; x++ )
for( y = posy ; y <= ptry ; y++ )
if( !f[x][y] )
{
cout << "Bad placement." << endl;
return 0;
}
ans++;
}

}
}
printf( "There are %d ships.\n" , ans );
}
return 0;
}

坑人！

测试数据 #0: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1652 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1588 KiB, score = 10
Accepted, time = 15 ms, mem = 1652 KiB, score = 100