ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1060. Перевертыш

Why WA?
Послано SunMoonStar 4 мар 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.