本文主要是介绍NOI 兔兔与蛋蛋的游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二维的一个最大匹配
program game;
type rec=record x,y:longint; end;
const numm:rec=(x:0;y:0);dx:array[1..4]of integer=(0,1,0,-1);dy:array[1..4]of integer=(1,0,-1,0);
var link:array[0..41,0..41]of rec;yy:array[0..41,0..41]of boolean;ans:array[0..400]of longint;a:array[0..41,0..41]of boolean;b:array[0..41,0..41]of byte;n,m:longint;
function find(x,y:longint):boolean; var r:byte; tmp:^rec;
beginfor r:=1 to 4 do if (not yy[x+dx[r]][y+dy[r]])and(a[x+dx[r]][y+dy[r]]) then begintmp:=@link[x+dx[r]][y+dy[r]];yy[x+dx[r]][y+dy[r]]:=true;if ((tmp^.x=0)and(tmp^.y=0))or(find(tmp^.x,tmp^.y)) then begintmp^.x:=x;tmp^.y:=y;exit(true);end;end; exit(false);
end;
function win(x,y:longint):boolean; var tmp,i,j:longint;
begintmp:=0;a[x][y]:=true;for i:=1 to n do for j:=1 to m doif ((i xor j) and 1=1)and a[i][j] then beginfillchar(yy,sizeof(yy),false);if find(i,j) then inc(tmp);end;fillchar(link,sizeof(link),0);a[x][y]:=false;for i:=1 to n do for j:=1 to m doif ((i xor j) and 1=1) and a[i][j] then beginfillchar(yy,sizeof(yy),false);if find(i,j) then dec(tmp);end;fillchar(link,sizeof(link),0);exit(tmp<>0);
end;
var i,j,x,y,k:longint; ch:char; now:boolean;
beginassign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);readln(n,m);for i:=1 to n do beginfor j:=1 to m do beginread(ch); case ch of'.':beginx:=i; y:=j;k:=(i xor j)and 1;end;'O':b[i][j]:=0;'X':b[i][j]:=1;end;end; readln;end;for i:=1 to n dofor j:=1 to m doa[i][j]:=((i xor j xor k)and 1 xor b[i][j]=1);readln(k);now:=win(x,y);a[x,y]:=false;for k:=1 to k do beginreadln(x,y);if now and find(x,y) then begininc(ans[0]); ans[ans[0]]:=k;end;a[x,y]:=false;readln(x,y);now:=find(x,y);a[x,y]:=false;end;writeln(ans[0]);for i:=1 to ans[0] do writeln(ans[i]);close(input);close(output);
end.
朴素的做法
program game;
constdx:array[1..4]of shortint=(1,0,-1,0);dy:array[1..4]of shortint=(0,1,0,-1);
varans:array[0..400]of longint;a:array[0..41,0..41]of boolean;b:array[1..40,1..40]of byte;
function find(const x,y:byte):boolean;
var r:byte;
beginfind:=false;a[x,y]:=false;for r:=1 to 4 doif a[x+dx[r]][y+dy[r]] thenif not find(x+dx[r],y+dy[r]) then beginfind:=true;break;end;a[x,y]:=true;
end;
var n,m,i,j,k,x,y:longint; ch:char; now:boolean;
beginassign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);readln(n,m);for i:=1 to n do beginfor j:=1 to m do beginread(ch); case ch of'.':beginx:=i; y:=j;k:=(i xor j)and 1;end;'O':b[i][j]:=0;'X':b[i][j]:=1;end;end; readln;end;for i:=1 to n dofor j:=1 to m doa[i][j]:=((i xor j xor k)and 1 xor b[i][j]=1);readln(k);now:=find(x,y);a[x,y]:=false;for k:=1 to k do beginreadln(x,y);a[x][y]:=false;if now and find(x,y) then begininc(ans[0]); ans[ans[0]]:=k;end;a[x][y]:=false;readln(x,y);a[x][y]:=false;now:=find(x,y);a[x][y]:=false;end;writeln(ans[0]);for i:=1 to ans[0] do writeln(ans[i]);close(input);close(output);
end.
这篇关于NOI 兔兔与蛋蛋的游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
