题解 - Vijos

0

厚黑教主 LV 8 @ 2009-03-13 20:22:53

错误程序,谁能看一下?

Program P1051;

const

a:array[1..12] of integer=(-2,-1,-1,-1,0,0,0,0,1,1,1,2);

b:array[1..12] of integer=(0,-1,0,1,-2,-1,1,2,-1,0,1,0);

var f:array[-1..102,-1..102] of char;

n,m,i,j,s:integer;

Procedure search(x,y:integer);

begin

f[x,y]:='-';

for i:=1 to 12 do

if (f[x+a[i],y+b[i]]='#')and(x+a[i]=1)and(y+b[i]=1)

then

begin

search(x+a[i],y+b[i]);

end;

end;

begin

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do read(f);

readln;

end;

s:=0;

for i:=1 to n do

for j:=1 to m do

if f='#'

then begin

inc(s);

search(i,j);

end;

writeln(s);

end.

0

试验 LV 8 @ 2009-03-11 16:57:33

program vijos1051;

const

a :array[1..12,1..2] of integer

=((-2,0),(-1,0),(2,0),(1,0),(0,1),(0,2),(0,-1),(0,-2),(-1,-1),(1,1),(-1,1),(1,-1));

var

i,j,n,m,sum:integer;

ch :array[-1..102,-1..102] of char;

procedure dfs(x,y:integer);

var i:integer;

begin

ch[x,y]:='-';

for i:=1 to 12 do

if(x+a0)and(y+a0)and(ch[x+a,y+a]='#')

then dfs(x+a,y+a);

end;

begin

sum:=0;

readln(n,m);

for i:= 1 to n do

begin

for j:= 1 to m do read(ch);

readln;

end;

for i:=1 to n do

for j:=1 to m do

begin

if (ch='#') then

begin dfs(i,j);

inc(sum); end;

end;

writeln(sum);

end.

0

dong LV 8 @ 2009-03-09 16:52:55

切记子程序不能占内存太大,否则就90分

0

gnaggnoyil LV 10 @ 2009-01-29 09:56:41

连FloodFill都不用!就暴力!

0

zgx LV 10 @ 2009-01-21 14:45:12

暴力才是王道！！！…^_^

0

木子日匀 LV 10 @ 2009-01-08 17:45:12

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次开太小了

第二次加个标志数组就过了 55555555555555

这个应该叫种子填充法

0

冰淇淋 LV 8 @ 2009-01-02 13:18:53

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

char a[100][100];

const int xx[]={-1,-1,-1,0,1,1,1,0,-2,0,2,0},

yy[]={-1,0,1,1,1,0,-1,-1,0,-2,0,2};

void go(int y,int x)

{

a[y][x]='-';

for(int i=0;i=0

&& x+xx[i]>=0 && y+yy[i]n>>m;

for(i=0;ia[i][j];

for(i=0;i

0

yyb LV 3 @ 2008-12-23 14:31:33

var

i,j,k,n,m:longint;

a:array[-1..102,-1..102]of char;

b:array[-1..102,-1..102]of boolean;

procedure li(x,y:longint);

var

i,j:longint;

begin

for i:=1 to 2 do

if (a[x+i,y]='#')and(not b[x+i,y])

then begin

　　 b[x+i,y]:=true;

　　 li(x+i,y);

　　 end;

0

2mc LV 10 @ 2008-12-21 19:14:15

找呀找呀找GiF，找到一个删一个呀，就知道有多少GF(怎么成GF了)!

0

330459659 LV 10 @ 2008-12-19 16:51:38

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

i,j,k,n,m:longint;

a:array[-1..102,-1..102]of char;

b:array[-1..102,-1..102]of boolean;

procedure li(x,y:longint);

var

i,j:longint;

begin

for i:=1 to 2 do

if (a[x+i,y]='#')and(not b[x+i,y])

then begin

b[x+i,y]:=true;

li(x+i,y);

end;

for i:=1 to 2 do

if (a[x,y+i]='#')and(not b[x,y+i])

then begin

b[x,y+i]:=true;

li(x,y+i);

end;

if (a[x+1,y+1]='#')and(not b[x+1,y+1])

then begin

b[x+1,y+1]:=true;

li(x+1,y+1);

end;

for i:=1 to 2 do

if (a[x-i,y]='#')and(not b[x-i,y])

then begin

b[x-i,y]:=true;

li(x-i,y);

end;

for i:=1 to 2 do

if (a[x,y-i]='#')and(not b[x,y-i])

then begin

b[x,y-i]:=true;

li(x,y-i);

end;

if (a[x+1,y-1]='#')and(not b[x+1,y-1])

then begin

b[x+1,y-1]:=true;

li(x+1,y-1);

end;

if (a[x-1,y+1]='#')and(not b[x-1,y+1])

then begin

b[x-1,y+1]:=true;

li(x-1,y+1);

end;

if (a[x-1,y-1]='#')and(not b[x-1,y-1])

then begin

b[x-1,y-1]:=true;

li(x-1,y-1);

end;

end;

begin

fillchar(b,sizeof(b),false);

readln(N,m);

for i:=1 to n do

begin

for j:=1 to m do

read(a);

readln;

end;

k:=0;

for i:=1 to n do

for j:=1 to m do

if (a='#')and(not b)

then begin inc(k); li(i,j); end;

write(k);

end.

Flag 　　 Accepted

题号　　P1051

类型(?) 　　搜索

通过　　2492人

提交　　6927次

通过率　　36%

难度　　1

提交讨论题解

0

Prince Frost LV 10 @ 2008-12-03 22:43:17

我用的非常非常非常非常非常非常非常非常非常非常非常非常暴力的搜。。。

但竟然AC了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

顺便66题纪念一下。。。

0

liruyuan LV 3 @ 2008-12-01 13:22:44

program Project1;

var

a:array[-1..100,-1..100]of char;

b:array[-1..100,-1..100]of integer;

i,j,m,n,s,t:longint;

procedure find(t,k:integer);

begin

b[t,k]:=p;

　　if ((a[t-2,k]='#')and(b[t-2,k]=0))then find(t-2,k);

　　if ((a[t-1,k]='#')and(b[t-1,k]=0))then find(t-1,k);

if ((a[t-1,k-1]='#')and(b[t-1,k-1]=0))then find(t-1,k-1);

if ((a[t-1,k+1]='#')and(b[t-1,k+1]=0))then find(t-1,k+1);

if ((a[t,k-2]='#')and(b[t,k-2]=0))then find(t,k-2);

if ((a[t,k+2]='#')and(b[t,k+2]=0))then find(t,k+2);

if ((a[t,k-1]='#')and(b[t,k-1]=0))then find(t,k-1);

if ((a[t,k+1]='#')and(b[t,k+1]=0))then find(t,k+1);

if ((a[t+2,k]='#')and(b[t+2,k]=0))then find(t+2,k);

if ((a[t+1,k]='#')and(b[t+1,k]=0))then find(t+1,k);

if ((a[t+1,k+1]='#')and(b[t+1,k+1]=0))then find(t+1,k+1);

if ((a[t+1,k-1]='#')and(b[t+1,k-1]=0))then find(t+1,k-1);

exit;

end;

begin

read(n,m);

for i:=1to n do

for j:=1to m do

read(a);

t:=1;k:=1; p:=1;

find(t,k);

write(s);

end.

0

zyc546 LV 8 @ 2008-11-29 18:58:49

R1080926 Accepted 100 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:54:05

R1080925 Unaccepted 30 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:53:06

R1080922 Unaccepted 30 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:52:16

R1080920 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:50:03

R1080917 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:48:04

R1080916 Unaccepted 30 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:46:42

R1080915 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:43:37

R1080855 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:06:32

R1080852 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 18:03:33

R1080828 Unaccepted 0 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:44:23

R1080826 No Compiled 0 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:43:31

R1080823 Unaccepted 0 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:39:25

R1080821 No Compiled 0 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:38:38

R1080814 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:32:36

R1080802 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:24:16

R1080789 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:18:40

R1080780 Unaccepted 20 From zyc546－

　P1051 GCC Vivid Puppy 2008-11-29 17:14:44

妈的

数组开小了

我的AC率

……暴减

以后数组能开多大开多大……

#include

typedef struct

{

int x;

int y;

}point;

void inqueue(int x,int y);

void dequeue();

void bfs(point *q);

point q[200000001];

int visited[1001][1001];

char map[1001][1001];

int head=1,tail=0,count=0;

int main(void)

{

int i,j,n,m;

scanf("%d%d",&n,&m);

for(i=0;i=0 && map[y-1][x+1]=='#'){inqueue(x+1,y-1);map[y-1][x+1]='-';}

if(map[y][x+1]=='#'){inqueue(x+1,y);map[y][x+1]='-';}

if(map[y][x+2]=='#'){inqueue(x+2,y);map[y][x+2]='-';}

if(map[y+1][x+1]=='#'){inqueue(x+1,y+1);map[y+1][x+1]='-';}

if(map[y+1][x]=='#'){inqueue(x,y+1);map[y+1][x]='-';}

if(map[y+2][x]=='#'){inqueue(x,y+2);;map[y+2][x]='-';}

if(x-1>=0 && map[y+1][x-1]=='#'){inqueue(x-1,y+1);map[y+1][x-1]='-';}

}

}

void inqueue(int x,int y)

{

tail++;

q[tail].x=x;

q[tail].y=y;

}

void dequeue()

{

head++;

}

0

Beta LV 6 @ 2008-11-28 22:01:08

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

就是一个广搜。

核心代码：

while i

0

二球中的二球 LV 3 @ 2008-11-13 14:30:15

水题深搜一遍带走~~~~~

procedure find(t,k:integer);

begin

b[t,k]:=p;

if ((a[t-2,k]='#')and(b[t-2,k]=0))then find(t-2,k);

if ((a[t-1,k]='#')and(b[t-1,k]=0))then find(t-1,k);

if ((a[t-1,k-1]='#')and(b[t-1,k-1]=0))then find(t-1,k-1);

if ((a[t-1,k+1]='#')and(b[t-1,k+1]=0))then find(t-1,k+1);

if ((a[t,k-2]='#')and(b[t,k-2]=0))then find(t,k-2);

if ((a[t,k+2]='#')and(b[t,k+2]=0))then find(t,k+2);

if ((a[t,k-1]='#')and(b[t,k-1]=0))then find(t,k-1);

if ((a[t,k+1]='#')and(b[t,k+1]=0))then find(t,k+1);

if ((a[t+2,k]='#')and(b[t+2,k]=0))then find(t+2,k);

if ((a[t+1,k]='#')and(b[t+1,k]=0))then find(t+1,k);

if ((a[t+1,k+1]='#')and(b[t+1,k+1]=0))then find(t+1,k+1);

if ((a[t+1,k-1]='#')and(b[t+1,k-1]=0))then find(t+1,k-1);

exit;

end;

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

a,b数组都定义的是-1 到 101 之间这样就不担心溢出了~~~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

zhaoyang LV 8 @ 2008-11-12 01:15:56

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

广搜，如果用深搜会出现堆栈溢出的情况.

0

So飞ar翔 LV 10 @ 2008-11-11 21:34:28

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

比较简单的。。。广搜。。。。

0

虾米姐姐2 LV 3 @ 2008-11-11 19:19:10

有谁能告诉我为什么我要用那么多时间？

感觉没有很多的重复计算嘛- -

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program jxh;

var

x,y,k,n,m,i,j,s,sum:integer;

a:array[1..100,1..100]of char;

b:array[1..10000,1..10000]of boolean;

mark:array[1..10000]of integer;

procedure dfs(x:integer);

var

i:integer;

begin

mark[x]:=1;

for i:=1 to m*n do

if (mark[i]=0) and b[x,i] then dfs(i);

end;

begin

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

read(a);

readln;

end;

for i:=1 to n do

for j:=1 to m do

if a='#' then

begin

s:=(i-1)*m+j;

if j>1 then b:=(a='#');

if j1 then b:=(a='#');

if i1) and (i>1) then b:=(a='#');

if (j>1) and (i

0

h4x3rotab LV 7 @ 2008-11-11 18:08:38

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

#define DARK 0

#define LIGHT 1

#define SECHD 2

int heigth,width;

int image[101][101];

void BFS(int x,int y);

int RegionScan();

int main(int argc, char **argv)

{

int x,y;

char ch;

cin>>x>>y;

heigth=y;

width=x;

for(int j=0;jch;

if(ch=='-')

image[i][j]=DARK;

else

image[i][j]=LIGHT;

}

coutargc;

return 0;

}

void BFS(int x,int y)

{

if(x=width||y=heigth) return;

if(image[x][y]==LIGHT)

{

image[x][y]=SECHD;

BFS(x-2,y); //1

BFS(x,y-2); //2

BFS(x,y+2); //3

BFS(x+2,y); //4

BFS(x-1,y); //5

BFS(x-1,y-1);

BFS(x,y-1);

BFS(x+1,y-1);

BFS(x+1,y); //9

BFS(x+1,y+1);

BFS(x,y+1); //B

BFS(x-1,y+1);

}

}

int RegionScan()

{

int regions=0;

for(int j=0;j

0

dementrock LV 8 @ 2008-11-11 12:10:02

if((x+move[i][0]>=0&&x+move[i][0]=0&&y+move[i][1]

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

还没有账户？

登录