黑白棋移动游戏

var
  f:array[1..70000,1..16]of longint;
  rec:array[1..70000]of record step,pre,ni,pi:longint; end;
  goal:array[1..16]of longint;
  al:array[1..70000]of record ni,pi:longint;   end;
  bo:array[0..65536]of boolean;
  head,tail,i,j,ans,num,x,x1,y1,x2,y2,t:longint;
  c:char;
procedure check;
var k:longint;  b:boolean;
begin
  b:=true;
  for k:=1 to 16 do
    if f[tail,k]<>goal[k] then b:=false;
  if b then
    begin
      ans:=rec[tail].step;
      writeln(ans);
      while tail<>1 do
        begin
          inc(num);
          al[num].ni:=rec[tail].ni;
          al[num].pi:=rec[tail].pi;
          tail:=rec[tail].pre;
        end;
      for k:=num downto 1 do
        begin
          x1:=(al[k].pi-1) mod 4 +1;
          y1:=(al[k].pi-1) div 4 +1;
          x2:=(al[k].ni-1) mod 4 +1;
          y2:=(al[k].ni-1) div 4 +1;
          if y1>y2 then
            begin
              t:=y1;  y1:=y2; y2:=t;
              t:=x1;  x1:=x2; x2:=t;
            end;
          if (y1=y2)and(x1>x2) then
            begin
              t:=y1;  y1:=y2; y2:=t;
              t:=x1;  x1:=x2; x2:=t;
            end;
          writeln(y1,x1,y2,x2);
        end;
      close(input);  close(output);
      halt;
    end;

end;




procedure doit;
begin
  head:=0;  tail:=1;

            x:=f[tail,1];
            for j:=2 to 16 do x:=x*2+f[tail,j];
            if bo[x] then dec(tail)
            else bo[x]:=true;
  repeat
    inc(head);
    for i:=1 to 16 do
      begin
        if (i+4<=16)and(f[head,i+4]<>f[head,i]) then
          begin
            inc(tail);
            for j:=1 to 16 do
              f[tail,j]:=f[head,j];
            f[tail,i]:=1-f[tail,i];
            f[tail,i+4]:=1-f[tail,i+4];;
            rec[tail].ni:=i+4;
            rec[tail].pi:=i;
            rec[tail].step:=rec[head].step+1;
            rec[tail].pre:=head;
            x:=f[tail,1];
            for j:=2 to 16 do x:=x*2+f[tail,j];
            if bo[x] then dec(tail)
            else bo[x]:=true;
            check;
          end;
        if (i-4>0)and(f[head,i-4]<>f[head,i]) then
          begin
            inc(tail);
            for j:=1 to 16 do
              f[tail,j]:=f[head,j];
            f[tail,i]:=1-f[tail,i];
            f[tail,i-4]:=1-f[tail,i-4];
            rec[tail].ni:=i-4;
            rec[tail].pi:=i;
            rec[tail].step:=rec[head].step+1;
            rec[tail].pre:=head;
            x:=f[tail,1];
            for j:=2 to 16 do x:=x*2+f[tail,j];
            if bo[x] then dec(tail)
            else bo[x]:=true;
            check;
          end;
        if (i mod 4 <>1)and(f[head,i-1]<>f[head,i]) then
          begin
            inc(tail);
            for j:=1 to 16 do
              f[tail,j]:=f[head,j];
            f[tail,i]:=1-f[tail,i];
            f[tail,i-1]:=1-f[tail,i-1];
            rec[tail].ni:=i-1;
            rec[tail].pi:=i;
            rec[tail].step:=rec[head].step+1;
            rec[tail].pre:=head;
            x:=f[tail,1];
            for j:=2 to 16 do x:=x*2+f[tail,j];
            if bo[x] then dec(tail)
            else bo[x]:=true;

            check;
          end;
        if (i mod 4<>0)and(f[head,i+1]<>f[head,i]) then
          begin
            inc(tail);
            for j:=1 to 16 do
              f[tail,j]:=f[head,j];
            f[tail,i]:=1-f[tail,i];
            f[tail,i+1]:=1-f[tail,i+1];;
            rec[tail].ni:=i+1;
            rec[tail].pi:=i;
            rec[tail].step:=rec[head].step+1;
            rec[tail].pre:=head;
            x:=f[tail,1];
            for j:=2 to 16 do x:=x*2+f[tail,j];
            if bo[x] then dec(tail)
            else bo[x]:=true;
            check;
          end;
      end;
  until head>tail;
end;

begin
  assign(input,‘game.in‘);  assign(output,‘game.out‘);
  reset(input);  rewrite(output);
  for i:=1 to 16 do
    begin
      read(c);
      val(c,f[1,i]);
      if i mod 4=0 then readln;
    end;
  for i:=1 to 16 do
    begin
      read(c);
      val(c,goal[i]);
      if i mod 4=0 then readln;
    end;
  doit;
end.
//做了这题才感觉搜索入门了