没什么好解释的,博弈论神题,代码都能看懂
var m,n,sx,sy,sum:longint; map:array[0..40,0..40] of char; id:array[0..40,0..40] of longint; win,del,v:array[0..2010] of boolean; g:array[0..2000,0..2000] of longint; link:array[0..2001] of longint; procedure get_inf; var i,j:longint; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do begin read(map[i][j]); if map[i][j]='.' then begin sx:=i;sy:=j; sum:=1;id[i][j]:=1; end; end; readln; end; for i:=1 to n do for j:=1 to m do if (map[i][j]='X') and ((i+j) and 1=(sx+sy) and 1) or (map[i][j]='O') and ((i+j) and 1 <> (sx+sy) and 1) then begin inc(sum); id[i][j]:=sum; end; for i:=1 to n do for j:=1 to m do if id[i][j]>0 then begin if id[i-1][j]>0 then begin inc(g[id[i][j],0]); g[id[i][j],g[id[i][j],0]]:=id[i-1][j]; inc(g[id[i-1][j],0]); g[id[i-1][j],g[id[i-1][j],0]]:=id[i][j]; end; if id[i][j-1]>0 then begin inc(g[id[i,j],0]); g[id[i,j],g[id[i,j],0]]:=id[i,j-1]; inc(g[id[i,j-1],0]); g[id[i,j-1],g[id[i,j-1],0]]:=id[i,j]; end; end; end; function find(x:longint):boolean; var i,y:longint; begin v[x]:=true; for y:=1 to g[x][0] do begin i:=g[x][y]; if not v[i] and not del[i] then begin v[i]:=true; if (link[i]=0) or find(link[i]) then begin link[i]:=x;link[x]:=i; exit(true); end; end; end; exit(false); end; function check:boolean; var t:longint; can:boolean; begin if link[id[sx,sy]]=0 then exit(false); del[id[sx,sy]]:=true; t:=link[id[sx,sy]]; link[t]:=0; link[id[sx,sy]]:=0; fillchar(v,sizeof(v),0); can:=find(t); if not can then begin link[t]:=id[sx,sy]; link[id[sx,sy]]:=t; end; del[id[sx,sy]]:=false; exit(not can); end; procedure main; var i,q,tot,x,y,t:longint; begin for i:=1 to sum do if link[i]=0 then begin fillchar(v,sizeof(v),0); find(i); end; read(q); tot:=0; for i:=1 to q do begin win[i]:=check; read(x,y); del[id[sx,sy]]:=true; t:=link[id[sx,sy]]; link[t]:=0; link[id[sx,sy]]:=0; fillchar(v,sizeof(v),0); find(t); sx:=x; sy:=y; if win[i] and check then inc(tot) else win[i]:=false; read(x,y); del[id[sx,sy]]:=true; t:=link[id[sx,sy]]; link[t]:=0; link[id[sx,sy]]:=0; fillchar(v,sizeof(v),0); find(t); sx:=x; sy:=y; end; writeln(tot); for i:=1 to q do if win[i] then writeln(i); end; begin get_inf; main; end.