/ Vijos / 题库 / 海战 /

# 122 条题解

• @ 2018-03-03 16:57:25

``````#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
return 0;
}
``````
• @ 2016-09-21 11:49:16
``````#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) ) {
return 0;
}
else k++;
}
printf("There are %d ships.\n",k-1);
return 0;
}
``````

写的好丑啊~~~~QAQ

• @ 2016-05-14 10:58:07
``````评测结果
编译成功

测试数据 #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);
return 0;
}
``````
• @ 2017-10-23 14:34:09

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

``````#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)
{
return 0;
}

}
}
cout<<"There are "<<mark<<" ships.";
return 0;
}

``````
• @ 2017-09-16 03:21:38
``````#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)
{
return 0;
}
x_min=100000,x_max=-1,y_min=100000,y_max=-1;
}
}
}
printf("There are %d ships.",num);
return 0;
}
``````
• @ 2017-05-07 22:29:17
``````/*
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 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)
}

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);
{
return 0;
}
}
}
cout<<"There are "<<ans<<" ships."<<endl;
return 0;
}

``````
• @ 2016-11-01 23:42:24

#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;
}

• @ 2016-08-23 08:54:51
``````#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] != '#') {
return 0;
}

}
cout<<"There are "<<count<<" ships.";
return 0;
}
``````
• @ 2015-10-17 08:40:40

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
for i:=1 to n do
begin
for j:=1 to m do
begin
if ch='.' then map[i,j]:=false;
if ch='#' then map[i,j]:=true;
end;
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
end;
end;
writeln('There are ',total,' ships.');
end.

• @ 2015-08-10 11:03:56

#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];
char str[2100];
void bfs(int x,int y)
{
int ulx=x,uly=y,drx=x,dry=y;
que[1].x=x,que[1].y=y,visit[x][y]=1;
{
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);
{
return 0;
}
}
printf("There are %d ships.\n",ans);
return 0;
}

• @ 2015-08-10 10:47:04

#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 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;
que[1].x=x;que[1].y=y;v[x][y]=1;
{
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);
}
}
}
}
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);
{
return 0;
}

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

• @ 2015-08-10 10:23:47

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

• @ 2015-08-04 21:25:08

记录信息
评测状态 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)
{
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);
}

• @ 2015-07-27 10:37:45

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
for i:=1 to r do
begin
for j:=1 to c do read(a[i,j]);
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
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.

• @ 2015-05-19 11:50:57

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.exit(0);
}

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

• @ 2015-03-16 17:46:33

#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;
}

• @ 2015-02-13 20:45:18

忘了这个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)break;
}
j=m;numk++;
}printf("There are %d ships.\n",numk);
return 0;
}

• @ 2014-11-05 16:17:18

对每一个点扫一遍就好了= = 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 (!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;
}

• @ 2014-10-31 21:38:37

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;
}

坑人！

• @ 2014-08-05 17:41:15

测试数据 #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

ID
1076

5

(无)

3107

1032

33%

10