INFOMAN брой 17

/*
 3-ти кръг на Републиканска Олимпиада по Информатика'2000
 Задача 1: КВАДРАТЧЕТА
 
 Задача: Имаме игрална дъска (фиг 1). Разрешени са 3 ходам които променят стойностите
 на няклко квадратчета на дъската - 0 става 1 и 1 става 0. Първият тип ход променя стойностите на 9 квадратчета, образуващи квадрат със страна 3
 (фиг 2). Вторият тип ход променя 5 квадратчета, разположени под формата на кръст (фиг 3)
 Третият тип ход променя всички квадратчета на дъската.
   0 0 0
 0 0 0 0 0            0 0 0       0
 0 0 0 0 0            0 0 0     0 0 0
 0 0 0 0 0            0 0 0       0
   0 0 0
   фиг 1              фиг 2     фиг 3
 Напишете програма, която по зададено състояние на дъската определя минималния брой ходове, необходими за да се получи това състовние, започвайки от началното (нулевото)

 Вход:                      Изход: 2
   0 1 0
 0 1 1 1 0
 0 1 0 1 0
 0 1 1 1 0
   1 1 1
*/

#include <stdio.h>
#include <math.h>

#define STACK 17000
#define INFINITY ~0

typedef unsigned long integer;

integer stack[STACK];
int out[5][5];
char inside[STACK];
integer output;
int a[5][5];

void proc1( int x, int y )
{
  int i, j;

  for( i = 0; i < 5; i++ )
    for ( j = 0; j < 5; j++ )
      out[i][j] = a[i][j];
  for( i = -1; i < 2; i++ )
    for ( j = -1; j < 2; j++ )
      out[x + i][y + j] = !a[x + i][y + j];
}

void proc2( int x, int y )
{
  int i, j;
  for( i = 0; i < 5; i++ )
    for ( j = 0; j < 5; j++ )
      out[i][j] = a[i][j];
  out[x - 1][y] = !a[x - 1][y];
  out[x][y - 1] = !a[x][y - 1];
  out[x][y] = !a[x][y];
  out[x + 1][y] = !a[x + 1][y];
  out[x][y + 1] = !a[x][y + 1];
}

void proc3()
{
  int i, j;

  for( i = 0; i < 5; i++ )
    for ( j = 0; j < 5; j++ )
      out[i][j] = !a[i][j];
}

integer enc( int a[5][5] )
{
  integer t = 0;

  t  = a[0][1] << 20;
  t += a[0][2] << 19;
  t += a[0][3] << 18;
  t += a[1][0] << 17;
  t += a[1][1] << 16;
  t += a[1][2] << 15;
  t += a[1][3] << 14;
  t += a[1][4] << 13;
  t += a[2][0] << 12;
  t += a[2][1] << 11;
  t += a[2][2] << 10;
  t += a[2][3] <<  9;
  t += a[2][4] <<  8;
  t += a[3][0] <<  7;
  t += a[3][1] <<  6;
  t += a[3][2] <<  5;
  t += a[3][3] <<  4;
  t += a[3][4] <<  3;
  t += a[4][1] <<  2;
  t += a[4][2] <<  1;
  t += a[4][3];

  return t;
}

void dec( integer x )
{
  a[0][1] = ( x & ( 1 << 20 )) >> 20;
  a[0][2] = ( x & ( 1 << 19 )) >> 19;
  a[0][3] = ( x & ( 1 << 18 )) >> 18;
  a[1][0] = ( x & ( 1 << 17 )) >> 17;
  a[1][1] = ( x & ( 1 << 16 )) >> 16;
  a[1][2] = ( x & ( 1 << 15 )) >> 15;
  a[1][3] = ( x & ( 1 << 14 )) >> 14;
  a[1][4] = ( x & ( 1 << 13 )) >> 13;
  a[2][0] = ( x & ( 1 << 12 )) >> 12;
  a[2][1] = ( x & ( 1 << 11 )) >> 11;
  a[2][2] = ( x & ( 1 << 10 ))>> 10;
  a[2][3] = ( x & ( 1 << 9 ))>> 9;
  a[2][4] = ( x & ( 1 << 8 ))>> 8;
  a[3][0] = ( x & ( 1 << 7 ))>> 7;
  a[3][1] = ( x & ( 1 << 6 ))>> 6;
  a[3][2] = ( x & ( 1 << 5 ))>> 5;
  a[3][3] = ( x & ( 1 << 4 ))>> 4;
  a[3][4] = ( x & ( 1 << 3 ))>> 3;
  a[4][1] = ( x & ( 1 << 2 ))>> 2;
  a[4][2] = ( x & ( 1 << 1 )) >> 1;
  a[4][3] = ( x & 1);
}

int get_step( int x )
{
  int t = 0, k;

  for( k = x; k > 0;)
  {
   k -= pow( 15, t );
   t++;
  }
  
  return t - 1;
}

int main( void )
{
  int i, j, w, r;

  freopen( "sqr.inp", "r", stdin );
//  freopen( "sqr.out", "w", stdout );

  for( i = 1; i < 4; i++ )
    scanf( "%d", &a[0][i] );
  for( i = 1; i < 4; i++ )
    for( j = 0; j < 5; j++ )
      scanf( "%d", &a[i][j] );
  for( i = 1; i < 4; i++ )
    scanf( "%d", &a[4][i] );
  output = enc( a );
    if( stack[0] == output )
    {
      printf( "0" );
      return 0;
    }

  stack[0] = 0;
  for( r = 0, w = 1; w != r - 1 || !r; r++)
  {
    dec( stack[r] );
    for( i = 1; i < 4; i++ )
      for( j = 1; j < 4; j++ )
        {
          proc2( i, j );
          stack[w] = enc( out );
          if( stack[w] == output )
          {
            printf( "%d", get_step( w ) );
            return 0;
          }
          if( !inside[w] ) inside[w++] = 1;
        }
        proc1( 1, 2 );
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
        proc1( 2, 1 );
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
        proc1( 2, 2 );
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
        proc1( 3, 2 );
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
        proc1( 2, 3 );
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
        proc3();
        stack[w] = enc( out );
        if( stack[w] == output )
        {
          printf( "%d", get_step( w ) );
          return 0;
        }
        if( !inside[w] ) inside[w++] = 1;
  }
  printf( "-1" );
  return 0;
}