Описание
Квадратный клетчатый лист бумаги размерами 2N×2N клеток начинают складывать следующим образом: сначала нижняя половина листа накладывается на верхнюю, а затем правая половина листа накладывается на его левую части. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8×8 клеток. Какие-то из клеток, сложенного таким образом листа, удаляются при помощи дырокола

После развертывания исходный лист распадется на некоторое количество связных частей, т.е. таких множеств клеток, что из любой клетки одного множества можно пройти по любой другой, переходя каждый раз на соседнюю по вертикали или горизонтали клетку. 

Задача
Напишите программу, вычисляющую число частей, на которые распадется лист


Входные данные
Первая строка входного файла содержит целое число N (4N500). В следующих S строках записана матрица 8х8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8x8

Выходные данные
Вывести в выходной файл искомое число частей


Например:

PUNCHER.IN
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 


PUNCHER.OUT
11


Идеи
Динамическое программирование, длинная арифметика

Комментарии
Каждую связную область сложенного листа (если смотреть на него сверху) закодируем двоичным числом b3b2b1b0. А именно, положим b0 равным единице, если эта область примыкает к нижней границе листа, и нулю в противном случае. Числа b1, b2 и b3 определим аналогичным образом для верхней, правой и левой границ листа соответственно. Тем самым, все области разбиваются на 16 типов в соответствии с их кодами. Теперь проанализируем, что происходит с областями при развертывании листа

Рассмотрит например, разгибание относительно нижней стороны. Легко заметить, что связная область типа b3b2b11 перейдет в связную область типа b3b2b1b1 (действительно, будет ли она прилегать К нижнему краю после разгибания зависит от того, прилегала ли ока к верхнему краю листа до разгибания). Связная область типа b3b2b10 после разгибания распадется на две. Одна из них будет иметь тот же тип b3b2b10, а другая - b3b20b1. Аналогично анализируется разгибание листа относительно правой стороны

Для решения задачи проделываем 2·N разгибаний, обратных произведенным при складывании листа сгибаниям. При этом на каждое шаге пересчитываем количество связных областей каждого из типов




Решение

{$A+,B-,D+,E-,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
 
{$M 65520,0,655360} 
 
Program puncher; 
Const Size=8; 
Var N:Integer; 
    A:Array[1..Size,1..Size] of Boolean; 
 
Procedure Init; 
Var i,j,k:Integer; 
Begin 
  Read(N); 
 
  For i:=1 to Size do 
    For j:=1 to Size do 
      Begin 
        Read(K); 
        A[i,j]:=K=1; 
      End
End(*Init*)
 
Const P=10000; 
      Len=100; 
      St=4; 
Type O=Array[0..Len] of Integer; 
 
Procedure Incr(Var A:O;B:O); 
Var i,R,E:Integer; 
    K:LongInt; 
    T:O; 
Begin 
  E:=B[0]; 
  If A[0]>=B[0] then 
    E:=A[0]; 
 
  R:=0; 
  For i:=1 to E do 
    Begin 
      K:=A[i]; 
      A[i]:=(K+B[i]+R) mod P; 
      R:=(K+B[i]+R) div P; 
    End
 
  A[0]:=E; 
  If R>0 then 
    Begin 
      Inc(A[0]); 
      A[A[0]]:=R; 
    End
End(*Incr*)
 
Var Part,Part1:Array[Boolean,Boolean,Boolean,Boolean] of O; 
    Is:Array[1..4] of Boolean; 
 
Procedure Rec(i,j:Integer); 
Begin 
  If (i<1) or (i>Size) or (j<1) or (j>Size) or A[i,j] then 
    Exit; 
 
  A[i,j]:=True; 
  If i=1 then 
    Is[2]:=True; 
  If j=1 then 
    Is[1]:=True; 
  If i=Size then 
    Is[4]:=True; 
  If j=SIze then 
    Is[3]:=True; 
 
  Rec(i+1,j); 
  Rec(i-1,j); 
  Rec(i,j+1); 
  Rec(i,j-1); 
End(*Rec*)
 
Procedure Inc(Var A:O); 
Var B:O; 
Begin 
  FillChar(B,SizeOf(B),0); 
  B[0]:=1; 
  B[1]:=1; 
  Incr(A,B); 
End(*Inc*)
 
Procedure InitPart; 
Var i,j:Integer; 
Begin 
  FillChar(Part,SizeOf(Part),0); 
 
  For i:=1 to Size do 
    For j:=1 to Size do 
      If Not A[i,j] then 
        Begin 
          FillChar(Is,SizeOf(Is),False); 
          Rec(i,j); 
 
          Inc(Part[Is[1],Is[2],Is[3],Is[4]]); 
        End
End(*InitPart*)
 
Procedure Calc(B1,B2,B3,B4:Boolean); 
Begin 
  Case B3 of 
    True:Case B4 of 
           True:Incr(Part[B1,B2,B1,B2],Part1[B1,B2,B3,B4]); 
           False:Begin 
                   Incr(Part[B1,False,B1,B2],Part1[B1,B2,B3,B4]); 
                   Incr(Part[B1,B2,B1,False],Part1[B1,B2,B3,B4]); 
                 End
         End
    False:Case B4 of 
            True:Begin 
                   Incr(Part[B1,B2,False,B2],Part1[B1,B2,B3,B4]); 
                   Incr(Part[False,B2,B1,B2],Part1[B1,B2,B3,B4]); 
                 End
            False:Begin 
                    Incr(Part[B1,B2,False,False],Part1[B1,B2,B3,B4]); 
                    Incr(Part[B1,False,False,B2],Part1[B1,B2,B3,B4]); 
                    Incr(Part[False,B2,B1,False],Part1[B1,B2,B3,B4]); 
                    Incr(Part[False,False,B1,B2],Part1[B1,B2,B3,B4]); 
                  End
          End
  End
End(*Calc*)
 
Procedure Solve; 
Var i:Integer; 
Begin 
  InitPart; 
 
  For i:=1 to N-3 do 
    Begin 
      Part1:=Part; 
      FillChar(Part,SizeOf(Part),0); 
      For Is[1]:=False to True do 
        For Is[2]:=False to True do 
          For Is[3]:=False to True do 
            For Is[4]:=False to True do 
              If Not((Part1[Is[1],Is[2],Is[3],Is[4],0]=0) or 
                     (Part1[Is[1],Is[2],Is[3],Is[4],0]=1) and 
                     (Part1[Is[1],Is[2],Is[3],Is[4],1]=0)) then 
                Calc(Is[1],Is[2],Is[3],Is[4]); 
    End
End(*Solve*)
 
Procedure Print(A:O); 
Var i:Integer; 
    S:String
Begin 
  Write(A[A[0]]); 
  For i:=A[0]-1 downto 1 do 
    Begin 
      Str(A[i],S); 
      While Length(S) do 
        S:='0'+S; 
      Write(S); 
    End
End(*Print*)
 
Procedure Done; 
Var Sum:O; 
Begin 
  FillChar(Sum,SizeOf(Sum),0); 
 
  For Is[1]:=False to True do 
    For Is[2]:=False to True do 
      For Is[3]:=False to True do 
        For Is[4]:=False to True do 
          Incr(Sum,Part[Is[1],Is[2],Is[3],Is[4]]); 
 
  Print(Sum); 
  WriteLn; 
End(*Done*)
 
Procedure Initialize; 
Begin 
  Assign(Input,'puncher.in'); 
  ReSet(Input); 
  Assign(Output,'puncher.out'); 
  ReWrite(Output); 
End(*Initialize*)
 
Procedure DoneAll; 
Begin 
  Close(Input); 
  Close(Output); 
End(*DoneAll*)
 
BEGIN 
  Initialize; 
   While not SeekEof do 
    Begin 
      Init; 
      Solve; 
      Done; 
    End
   DoneAll; 
END.


© Особенности национальных задач по информатике