ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1060. Flip Game

Why WA?
Posted by SunMoonStar 4 Mar 2003 19:15
program p1060;
const maxx=66000;
type tnum=array [1..16] of shortint;
     rec=record map:tnum; dep,pre:longint; end;
     arr1=array [1..maxx] of rec;
     arr2=array [0..maxx] of boolean;
var link:arr1; h:arr2;

function ten(t:tnum):longint;
var i:byte; x:longint;
begin
     x:=0;
     for i:=1 to 16 do
       x:=x+trunc(exp((i-1)*ln(2)))*t[i];
     ten:=x;
end;

function finish(t:tnum):boolean;
var i:byte;
begin
     for i:=1 to 16 do
       if (t[i]<>t[1]) then begin finish:=false; exit; end;
     finish:=true;
end;

procedure init;
var i,j:byte; ch:char;
begin
     for i:=1 to 4 do
       begin
         for j:=1 to 4 do
           begin
             read(ch); if (ch='w') then link[1].map[4*(i-1)+j]:=0
else link[1].map[4*(i-1)+j]:=1;
           end;
         readln;
       end;
     link[1].pre:=0; link[1].dep:=1;
     if finish(link[1].map) then begin writeln(0); readln; halt; end;
     fillchar(h,sizeof(h),false);
end;

procedure change(var t:tnum; i:byte);
begin
     if (t[i]=1) then t[i]:=0 else t[i]:=1;
end;

procedure solve;
var closed,open,w:LONGINT; t:tnum; i:byte;
begin
     closed:=0; open:=1;
     repeat
       inc(closed);
       for i:=1 to 16 do
           begin
             t:=link[closed].map;
             change(t,i);
             if ((i-1) mod 4<>0) then change(t,i-1); if (i>4)  then
change(t,i-4);
             if (i<13) then change(t,i+4); if (i mod 4<>0) then
change(t,i+1);
             w:=ten(t);
             if (not h[w]) then
               begin
                 inc(open); h[w]:=true;
                 link[open].map:=t; link[open].pre:=closed; link
[open].dep:=closed+1;
               end;
             if finish(t) then begin writeln(link[closed].dep);
readln; halt; end;
           end;
     until (closed>=open);
end;

begin
     init;
     solve;
     writeln('Impossible');
     readln;
end.