讨论 / 120行暴力75分...
工藤柯南 2013-06-26 02:57:00
点我顶贴 收藏 删除
var

a,aa:array [0..50,0..50] of longint;

win1,win2:array [0..1000] of boolean;

v:array [0..50,0..50] of boolean;

wrong:array [0..1000] of longint;

n,m,k,spacex,spacey,path:longint;

procedure init;

var

i,j:longint; ch:char;

begin

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

begin

read(ch);

if ch='.' then a[i,j]:=0 else if ch='O' then a[i,j]:=1 else a[i,j]:=2;

if ch='.' then begin spacex:=i; spacey:=j; end;

end;

readln;

end;

end;

function dfs1(x,y:longint):boolean; forward;

function dfs2(x,y:longint):boolean;

var

flag:boolean;

begin

inc(path); if path>10000 then begin exit(false); exit; end;

v[x,y]:=false; flag:=false;

if (x+1<=n) and (a[x+1,y]=2) and v[x+1,y] then

begin

a[x,y]:=a[x+1,y]; a[x+1,y]:=0;

if dfs1(x+1,y)=false then begin a[x+1,y]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x+1,y]:=a[x,y]; a[x,y]:=0;

end;

if (x-1>=1) and (a[x-1,y]=2) and v[x-1,y] then

begin

a[x,y]:=a[x-1,y]; a[x-1,y]:=0; flag:=true;

if dfs1(x-1,y)=false then begin a[x-1,y]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x-1,y]:=a[x,y]; a[x,y]:=0;

end;

if (y+1<=m) and (a[x,y+1]=2) and v[x,y+1] then

begin

a[x,y]:=a[x,y+1]; a[x,y+1]:=0; flag:=true;

if dfs1(x,y+1)=false then begin a[x,y+1]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x,y+1]:=a[x,y]; a[x,y]:=0;

end;

if (y-1>=1) and (a[x,y-1]=2) and v[x,y-1] then

begin

a[x,y]:=a[x,y-1]; a[x,y-1]:=0; flag:=true;

if dfs1(x,y-1)=false then begin a[x,y-1]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x,y-1]:=a[x,y]; a[x,y]:=0;

end;

v[x,y]:=true;

exit(false);

end;

function dfs1(x,y:longint):boolean;

var

flag:boolean;

begin

inc(path); if path>10000 then begin exit(false); exit; end;

v[x,y]:=false; flag:=false;

if (x+1<=n) and (a[x+1,y]=1) and v[x+1,y] then

begin

a[x,y]:=a[x+1,y]; a[x+1,y]:=0; flag:=true;

if dfs2(x+1,y)=false then begin a[x+1,y]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x+1,y]:=a[x,y]; a[x,y]:=0;

end;

if (x-1>=1) and (a[x-1,y]=1) and v[x-1,y] then

begin

a[x,y]:=a[x-1,y]; a[x-1,y]:=0; flag:=true;

if dfs2(x-1,y)=false then begin a[x-1,y]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x-1,y]:=a[x,y]; a[x,y]:=0;

end;

if (y+1<=m) and (a[x,y+1]=1) and v[x,y+1] then

begin

a[x,y]:=a[x,y+1]; a[x,y+1]:=0; flag:=true;

if dfs2(x,y+1)=false then begin a[x,y+1]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x,y+1]:=a[x,y]; a[x,y]:=0;

end;

if (y-1>=1) and (a[x,y-1]=1) and v[x,y-1] then

begin

a[x,y]:=a[x,y-1]; a[x,y-1]:=0; flag:=true;

if dfs2(x,y-1)=false then begin a[x,y-1]:=a[x,y]; a[x,y]:=0; v[x,y]:=true; exit(true); end;

a[x,y-1]:=a[x,y]; a[x,y]:=0;

end;

v[x,y]:=true;

exit(false);

end;

procedure main;

var

i,x,y,tot:longint;

begin

fillchar(v,sizeof(v),true); tot:=0; path:=0;

aa:=a; win1[0]:=dfs1(spacex,spacey); a:=aa; readln(k);

for i:=1 to k do

begin

readln(x,y); a[spacex,spacey]:=a[x,y]; a[x,y]:=0; spacex:=x; spacey:=y;

path:=0; aa:=a; fillchar(v,sizeof(v),true); win2[i]:=dfs2(spacex,spacey); a:=aa;

readln(x,y); a[spacex,spacey]:=a[x,y]; a[x,y]:=0; spacex:=x; spacey:=y;

path:=0; aa:=a; fillchar(v,sizeof(v),true); win1[i]:=dfs1(spacex,spacey); a:=aa;

end;

for i:=1 to k do

if win1[i-1] and win2[i] then

begin

inc(tot); wrong[tot]:=i;

end;

writeln(tot);

for i:=1 to tot do writeln(wrong[i]);

end;

begin

assign(input,'game.in');

reset(input);

assign(output,'game.out');

rewrite(output);

init;

main;

close(input);

close(output);

end.

#1 小胖无敌@2013-06-22 20:31:00
回复 删除
很想认识一下

你一定要参加noi吧,天天看你刷oi的题,好厉害啊,我是一个菜鸟,对noi也感兴趣,可不可以加你啊?我想加你哦,本人qq 374239176,求柯南加,其它人,就算了,太大牛也不敢跟人唠嗑,我很菜啊,还有,暴搜太帅了,适合我,可我这题暴搜只有25分啊,求柯南指点,像我这样的压根就不打算ac这个题,拜托了

#2 小胖无敌@2013-06-24 02:19:00
回复 删除
不理我,哼哼

我也暴力75了,嘿嘿,真心想认识一下来着

#3 darkfire@2013-06-26 02:57:00
回复 删除
啥?

哪一题??

查看更多回复
提交回复