Wikioi P1004 四子连棋 Wikioi

要我说，Wikioi里面比较坑爹的题目，宽搜题算一种，代码量大而且一旦出错很难找到错误之所在。
四子连棋这一题是4*4的棋盘，有2个空位，我们可以用数组的[0,1],[0,2],[0,3],[0,4]来记录这两个空位的横纵坐标，并设置增量数组控制棋的走向。
还有一个坑爹的就是黑白棋要轮流走，这个我们可以将数组[0,0]位置标记为上一次走棋的颜色，初始[0,0]=-1，若黑色1白色0，那么只要上一次的[0,0]值与这一次将要走的棋的代码（0或1）不同，就可以拓展这种状态。
至于判重，我先想到用一个大三进制数来判重，后来发现如果用boolean数组内存会爆，作罢，老老实实开一个很大的“4*4数组”数组一个一个比较吧。。。
附Pascal代码：

program P1004; type arr=array[0..4,0..4] of integer; const dx:array[1..4] of longint=(1,-1,0,0); dy:array[1..4] of longint=(0,0,1,-1); //增量数组。。。 var f:array[1..500000,0..4,0..4] of integer; a:Arr; i,j,x_1,x_2,y_1,y_2:longint; c:char; flag:boolean; //标记是否为为第一个出现的空位 function Complete(a:arr):boolean; //判断是否已经完成了变换 var i,j:longint; flag:boolean; begin for i:=1 to 4 do begin flag:=true; for j:=1 to 4 do if a[i,j]<>1 then flag:=false; if flag then exit(true); flag:=true; for j:=1 to 4 do if a[i,j]<>0 then flag:=false; if flag then exit(true); end; flag:=true; for i:=1 to 4 do if a[i,i]<>1 then flag:=false; if flag then exit(true); flag:=true; for i:=1 to 4 do if a[i,4-i+1]<>1 then flag:=false; if flag then exit(true); flag:=true; for i:=1 to 4 do if a[i,i]<>0 then flag:=false; if flag then exit(true); flag:=true; for i:=1 to 4 do if a[i,4-i+1]<>0 then flag:=false; if flag then exit(true); exit(false); end; function Same(a,b:arr):boolean; //判重 var i,j:longint; begin for i:=1 to 4 do for j:=1 to 4 do if a[i,j]<>b[i,j] then exit(false); exit(true); end; procedure work(k,last,now:longint); var a:arr; x,y,i,j,kk,noww,x1,y1,x2,y2,tmp:longint; flag:boolean; begin noww:=now; for i:=last to noww do begin x1:=f[i,0,1]; y1:=f[i,0,2]; x2:=f[i,0,3]; y2:=f[i,0,4]; for j:=1 to 4 do begin a:=f[i]; x:=x1+dx[j]; y:=y1+dy[j]; //对于当前情况的第一个空位进行状态拓展 if (x>0)and(y>0)and(x<5)and(y<5)and(a[x,y]<>a[0,0])and(a[x,y]<>2) then begin tmp:=a[x,y]; a[x,y]:=2; a[x1,y1]:=tmp; flag:=true; for kk:=1 to noww do if Same(f[kk],a) then flag:=false; if flag then begin inc(now); a[0,0]:=tmp; a[0,1]:=x; a[0,2]:=y; if Complete(a) then begin writeln(k); readln; readln; halt; end; f[now]:=a; end; end; a:=f[i]; x:=x2+dx[j]; y:=y2+dy[j]; //对于当前情况的第二个空位进行状态拓展 if (x>0)and(y>0)and(x<5)and(y<5)and(a[x,y]<>a[0,0])and(a[x,y]<>2) then begin tmp:=a[x,y]; a[x,y]:=2; a[x2,y2]:=tmp; flag:=true; for kk:=1 to noww do if Same(f[kk],a) then flag:=false; if flag then begin inc(now); a[0,0]:=tmp; a[0,3]:=x; a[0,4]:=y; if Complete(a) then begin writeln(k); readln; readln; halt; end; f[now]:=a; end; end; end; end; work(k+1,noww+1,now); end; begin flag:=true; for i:=1 to 4 do begin for j:=1 to 4 do begin read(c); if c='B' then a[i,j]:=1; if c='O' then begin a[i,j]:=2; if flag then begin x_1:=i; y_1:=j; flag:=false; end else begin x_2:=i; y_2:=j; end; end; if c='W' then a[i,j]:=0; end; readln; end; a[0,0]:=-1; a[0,1]:=x_1; a[0,2]:=y_1; a[0,3]:=x_2; a[0,4]:=y_2; f[1]:=a; work(1,1,1); end.

【Wikioi P1004 四子连棋】