题解 - Vijos

0

dragonfly LV 8 @ 2009-06-17 20:57:03

请教各位大牛...

用的BFS,但不知找到并扩展一个亮点后,如何从头开始另找一亮点...

核心代码

repeat

for i:=1 to n do begin

for j:=1 to m do if a='#' then begin

fillchar(f,sizeof(f),0); //队列初始化

rudui(i,j); //入队并标记'-'过程,略

bfs; //八个方向搜索,经检查无误

end;

inc(tot); //图案数

until (i=n) and (j=m); //遍历完退出

希望各位大牛解疑,感激不尽!

0

张冀 LV 8 @ 2009-06-17 15:47:12

if t1+1=1 then if a[t1-2,t2]='#' then dd(t1-2,t2);

if t2+1=1 then if a[t1,t2-2]='#' then dd(t1,t2-2);

if (t1+1=1) then if a[t1-1,t2-1]='#' then dd(t1-1,t2-1);

真强汗~~~~

0

jack7286434 LV 9 @ 2009-06-16 11:46:24

简单宽搜

大家加油~~

0

亦凡 LV 8 @ 2009-06-15 10:46:45

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

谁散布谣言说深搜不能过，秒杀！！！！！！！

深搜很简单吗！

0

327888145 LV 8 @ 2009-06-08 20:51:12

program sa（input,output);

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

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

var

board:array[-1..1000,-1..1000] of char;

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

procedure print;

var a1,b1:integer;

begin

for a1:=1 to n do begin

for b1:=1 to m do

write(board[a1,b1]);

writeln;

end;

end;

procedure remove(x,y:integer);

var a:integer;

begin

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

for a:=1to 12 do begin

if board[x+dx[a],y+dy[a]]='#' then remove(x+dx[a],y+dy[a]);

end;{for}

end;{remove}

begin

assign(input,'sa.in');

reset(input);

assign(output,'sa.out');

rewrite(output);

readln(n,m);

for i:=1 to n do begin

for j:=1 to m do

read(board);

readln;

end;{in}

close(input);

fillchar(board,sizeof(board),'-');

sum:=0;

for i:=1 to n do

for j:=1 to m do begin

if board='#' then begin

remove(i,j);

inc(sum);

end;

end;{do it}

writeln(sum);

close(output);

end.{main}

0

灰原哀 LV 10 @ 2009-06-08 18:05:11

program sherry;

var

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

a:array[0..1000,0..1000] of char;

procedure dd(t1,t2:longint);

var

i,j:longint;

begin

a[t1,t2]:='-';

if t1+1=1 then if a[t1-2,t2]='#' then dd(t1-2,t2);

if t2+1=1 then if a[t1,t2-2]='#' then dd(t1,t2-2);

if (t1+1=1) then if a[t1-1,t2-1]='#' then dd(t1-1,t2-1);

end;

begin

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='#' then

begin

inc(k);

dd(i,j);

end;

writeln(k);

end.

0

noipyubin LV 4 @ 2009-06-02 14:44:09

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

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

a:array[0..1000,0..1000] of char;

procedure dd(t1,t2:longint);

var

i,j:longint;

begin

a[t1,t2]:='-';

if t1+1=1 then if a[t1-2,t2]='#' then dd(t1-2,t2);

if t2+1=1 then if a[t1,t2-2]='#' then dd(t1,t2-2);

if (t1+1=1) then if a[t1-1,t2-1]='#' then dd(t1-1,t2-1);

end;

begin

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='#' then

begin

inc(k);

dd(i,j);

end;

writeln(k);

end.

一次AC，编的EASY

0

黄瓜人酋长 LV 8 @ 2009-05-30 08:19:11

BFS程序，自测全过……

可为啥一交就全出0呢……

大牛给看一下

#include

int n,m,top=0,ch;

int from=0,end=0,q[10000];

int heng[12]={-2,-1,-1,-1,0,0,0,0,1,1,1,2};

int zong[12]={0,-1,0,1,-2,-1,1,2,-1,0,1,0};

char a[100][100];

int check()

{

int x=0;

while(x

0

MYM_Lee LV 7 @ 2009-05-21 20:09:03

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

PROGRAM Christmas;

CONST

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

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

TYPE

node=record

x,y:longint;

end;

VAR

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

list:array[1..10000]of node;

i,j,n,m,count,open,head:longint;

s:string;

PROCEDURE expand(k:longint);

Var

i,j,x,y:longint;

Begin

for i:=1 to 12 do

begin

x:=list[k].x+dx[i];

y:=list[k].y+dy[i];

if (x>=1)and(x=1)and(y

0

linyinghao LV 8 @ 2009-05-18 19:00:27

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1051;

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

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

ch:char;

procedure p(x,y:integer);

begin

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

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

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

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

if (x+2=1) and (a[x-2,y]='#') then p(x-2,y);

if (y+2=1) and (a[x,y-2]='#') then p(x,y-2);

exit;

end;

begin

fillchar(a,sizeof(a),0);

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

inc(sum);

p(i,j);

end;

write(sum);

end.

0

abrahamlee LV 8 @ 2009-05-18 13:06:03

本题简单搜索.搜索方向定义为12个(分别为左2,左,左上,上,上2,右上,右,右2,右下,下,下2,左下),来表示迈哈顿距离.

只要搜到"#"就继续,否则停止.

一边搜索一边将已经搜索过的'#'置为'-'.

0

wzc1995 LV 10 @ 2009-05-17 02:01: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;

char a[100][100];

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

yy[15]={-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;

s=0;

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

for(i=0;i

0

tianjiao LV 5 @ 2009-05-12 17:24:30

#include

char a[100][100];

int n,m;

int find(x,y)

{

if(a[x][y]=='#')

{

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

if(x-2>=0&&a[x-2][y]=='#')

find(x-2,y);

if(x-1>=0&&a[x-1][y]=='#')

find(x-1,y);

if(x+1=0&&a[x][y-2]=='#')

find(x,y-2);

if(y+1=0&&a[x-1][y-1]=='#')

find(x-1,y-1);

if(x-1>=0&&y+1=0&&y-1>=0&&a[x-1][y-1]=='#')

find(x-1,y-1);

if(x+1

0

WJΨ LV 7 @ 2009-05-08 15:53:35

BFS+队列

0

xb45 LV 8 @ 2009-05-08 13:13:54

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

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

0

yali-2008 LV 8 @ 2009-05-04 13:45:01

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

int n,m,count;

char map[100][100];

void Find(int a,int b)

{

map[a]='-';

if(a-2>=0&&map[a-2]=='#')

Find(a-2,b);

if(a-1>=0&&map[a-1]=='#')

Find(a-1,b);

if(a-1>=0&&b+1=0&&b-1>=0&&map[a-1]=='#')

Find(a-1,b-1);

if(b+2=0&&map[a]=='#')

Find(a,b-2);

if(a+1

0

yali-v LV 9 @ 2009-05-04 13:42:24

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

sjh LV 7 @ 2009-05-03 19:01:53

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

henry12 LV 5 @ 2009-04-13 15:53:54

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.

0

xudyh LV 10 @ 2009-04-13 14:17:36

深搜还广搜呢？

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

还没有账户？

登录