#include <stdio.h>

int brpoz=0;
int brpozab=0;

int kraj(int t[3][3], int *p)
{
  int i;
  int j;
  
  for(i=0; i<3; i++)
    if(t[0][i] && t[0][i]==t[1][i] && t[1][i]==t[2][i])
    {
      if(p)
        *p=t[0][i];
      return 1;
    }
    

  for(i=0; i<3; i++)
    if(t[i][0] && t[i][0]==t[i][1] && t[i][1]==t[i][2])
    {
      if(p)
        *p=t[i][0];
      return 1;
    }
  
  if(t[0][0] && t[0][0]==t[1][1] && t[1][1]==t[2][2])
  {
    if(p)
      *p=t[0][0];
    return 1;
  }

  if(t[0][2] && t[0][2]==t[1][1] && t[1][1]==t[2][0])
  {
    if(p)
      *p=t[0][2];
    return 1;
  }

  for(i=0; i<3; i++)
  {
    for(j=0; j<3; j++)
      if(t[i][j]==0)
        break;
    if(j<3)
      break;
  }
  
  if(i==3)
  {
    if(p)
      *p=0;
    return 1;  
  }
  
  return 0;
}

int min(int t[3][3]);

int max(int t[3][3], int *px, int *py)
{
  int i,j;
  int vrednost;
  int maxv=-2;
  int m;
  
  brpoz++;
  
  if(kraj(t,&vrednost))
    return vrednost;
  
  for(i=0; i<3; i++)
    for(j=0; j<3; j++)
      if(t[i][j])
        continue;
      else
      {
        t[i][j]=1;
        if((m=min(t))>maxv)
        {
          maxv=m;
          if(px)
            *px=i;
          if(py)
            *py=j;
        }
        t[i][j]=0;
      }  
  return maxv;
}

int min(int t[3][3])
{
  int i,j;
  int vrednost;
  int minv=2;
  int m;
  
  brpoz++;
  
  if(kraj(t,&vrednost))
    return vrednost;
  
  for(i=0; i<3; i++)
    for(j=0; j<3; j++)
      if(t[i][j])
        continue;
      else
      {
        t[i][j]=-1;
        if((m=max(t,NULL,NULL))<minv)
          minv=m;
        t[i][j]=0;
      }  
  return minv;
}



void minimax(int t[3][3], int *px, int *py)
{
  max(t,px,py);
}



int minab(int t[3][3], int a, int b);

int maxab(int t[3][3], int a, int b, int *px, int *py)
{
  int i,j;
  int vrednost;
  int maxv=-2;
  int m;
  
  brpozab++;
  
  if(kraj(t,&vrednost))
    return vrednost;
  
  for(i=0; i<3; i++)
    for(j=0; j<3; j++)
      if(t[i][j])
        continue;
      else
      {
        t[i][j]=1;
        if((m=minab(t,a,b))>maxv)
        {
          maxv=m;
          if(px)
            *px=i;
          if(py)
            *py=j;
        }
        t[i][j]=0;
        
        if(maxv>=b)
          return maxv;
        if(maxv>a)
          a=maxv;
        
      }  
  return maxv;
}

int minab(int t[3][3], int a, int b)
{
  int i,j;
  int vrednost;
  int minv=2;
  int m;
  
  brpozab++;
  
  if(kraj(t,&vrednost))
    return vrednost;
  
  for(i=0; i<3; i++)
    for(j=0; j<3; j++)
      if(t[i][j])
        continue;
      else
      {
        t[i][j]=-1;
        if((m=maxab(t,a,b,NULL,NULL))<minv)
          minv=m;
        t[i][j]=0;
        if(minv<=a)
          return minv;
        if(minv<b)
          b=minv;
      }  
  return minv;
}



void minimaxab(int t[3][3], int *px, int *py)
{
  maxab(t,-2,2,px,py);
}



int main(int argc, char *argv[])
{
  int tabla[3][3]={{0,0,0},{0,0,0},{0,0,0}};
  int potez=-1;
  int pobednik;
  int px, py;
  int i,j;
  
  while(1)
  {
    for(i=0; i<3; i++)
    {
      for(j=0; j<3; j++)
      {
        if(tabla[i][j]==1)
          putchar('O');
        else if(tabla[i][j]==-1)
          putchar('X');
        else
          putchar('.');
        putchar(' ');
      }
      putchar('\n');
    }
    putchar('\n');
    
    if(kraj(tabla,&pobednik))
    {
      if(pobednik==1)
        printf("Pobedio je O.\n");
      else if(pobednik==-1)
        printf("Pobedio je X.\n");
      else
        printf("Nereseno.\n");
      break;
    }
    
    if(potez==-1)
    {
      scanf("%d %d",&px, &py);
      if(px<0 || px>2 || py<0 || py>2 || tabla[px][py])
      {
        printf("Los potez!\n");
        continue;
      }
    }
    else
    {
      brpoz=0;
      brpozab=0;
      minimax(tabla,NULL,NULL);
      minimaxab(tabla,&px,&py);
      printf("Broj poziva bez ab-odsecanja: %d.\n", brpoz);
      printf("Broj poziva sa ab-odsecanjem: %d.\n", brpozab);
    }
    
    tabla[px][py]=potez;
    potez=-potez; 
  }
  return 0;
}