sb↓

#include <bits/stdc++.h>
using namespace std;

struct node2
{
  int x,y;
};

int a[19][19];
int b[19][19];
node2 blck[190],whte[190];
node2 leckb[190],leckw[190];
int lft=9,riht=9,upp=9,dwn=9,lcnt=-1,rcnt=-1,cnt=-1,cnt2=-1;
node2 best;
int bs,nowbs;

void test()
{
  cout << lft << " " << riht << " " << upp << " " << dwn << endl;
  cout << cnt << endl;
  cout << cnt2 << endl;
  cout << lcnt << endl;
  cout << rcnt << endl;
}

node2 three_enemy(int c[][19],int pd,int nothi,node2 aa[])
{
  if(pd==-1)
  {
    for(int i=0; i<=lcnt; i++)
    {
      int x=aa[i].x,y=aa[i].y;
      if(c[x+1][y+1]==pd && c[x-1][y-1]==pd)
      {
        if(c[x+2][y+2]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y+2;
          return ps;
        }
        if(c[x-2][y-2]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y-2;
          return ps;
        }
      }
      if(c[x-1][y+1]==pd && c[x+1][y-1]==pd)
      {
        if(c[x-2][y+2]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y+2;
          return ps;
        }
        if(c[x+2][y-2]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y-2;
          return ps;
        }
      }
      if(c[x-1][y]==pd && c[x+1][y]==pd)
      {
        if(c[x-2][y]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y;
          return ps;
        }
        if(c[x+2][y]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y;
          return ps;
        }
      }
      if(c[x][y-1]==pd && c[x][y+1]==pd)
      {
        if(c[x][y-2]==0)
        {
          node2 ps;
          ps.x=x;
          ps.y=y-2;
          return ps;
        }
        if(c[x][y+2]==0)
        {
          node2 ps;
          ps.x=x;
          ps.y=y+2;
          return ps;
        }
      }
    }
  }
  else
  {
    for(int i=0; i<=rcnt; i++)
    {
      int x=aa[i].x,y=aa[i].y;
      if(c[x+1][y+1]==pd && c[x-1][y-1]==pd)
      {
        if(c[x+2][y+2]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y+2;
          return ps;
        }
        if(c[x-2][y-2]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y-2;
          return ps;
        }
      }
      if(c[x-1][y+1]==pd && c[x+1][y-1]==pd)
      {
        if(c[x-2][y+2]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y+2;
          return ps;
        }
        if(c[x+2][y-2]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y-2;
          return ps;
        }
      }
      if(c[x-1][y]==pd && c[x+1][y]==pd)
      {
        if(c[x-2][y]==0)
        {
          node2 ps;
          ps.x=x-2;
          ps.y=y;
          return ps;
        }
        if(c[x+2][y]==0)
        {
          node2 ps;
          ps.x=x+2;
          ps.y=y;
          return ps;
        }
      }
      if(c[x][y-1]==pd && c[x][y+1]==pd)
      {
        if(c[x][y-2]==0)
        {
          node2 ps;
          ps.x=x;
          ps.y=y-2;
          return ps;
        }
        if(c[x][y+2]==0)
        {
          node2 ps;
          ps.x=x;
          ps.y=y+2;
          return ps;
        }
      }
    }
  }
  return (node2)
  {
    -1,-1
  };
}

int end(int c[][19],node2 d[],node2 e[],int cnt3,int cnt4)
{
  for(int i=0; i<=cnt3; i++)
  {
    int x=d[i].x,y=d[i].y;
    if(c[x][y]==c[x+1][y+1] && c[x+1][y+1]==c[x+2][y+2] && c[x+1][y+1]==c[x-1][y-1] && c[x+1][y+1]==c[x-2][y-2])
    {
      return 1;
    }
    if(c[x][y]==c[x-1][y+1] && c[x-1][y+1]==c[x-2][y+2] && c[x-1][y+1]==c[x+1][y-1] && c[x+1][y-1]==c[x+2][y-2])
    {
      return 1;
    }
    if(c[x][y]==c[x+1][y] && c[x][y]==c[x+2][y] && c[x][y]==c[x-1][y] && c[x][y]==c[x-2][y])
    {
      return 1;
    }
    if(c[x][y]==c[x][y+1] && c[x][y]==c[x][y-1] && c[x][y]==c[x][y+2] && c[x][y]==c[x][y-2])
    {
      return 1;
    }
  }
  for(int i=0; i<=cnt4; i++)
  {
    int x=e[i].x,y=e[i].y;
    //cout << x << y << endl;
    if(c[x][y]==c[x+1][y+1] && c[x+1][y+1]==c[x+2][y+2] && c[x+1][y+1]==c[x-1][y-1] && c[x+1][y+1]==c[x-2][y-2])
    {
      return -1;
    }
    if(c[x][y]==c[x-1][y+1] && c[x-1][y+1]==c[x-2][y+2] && c[x-1][y+1]==c[x+1][y-1] && c[x+1][y-1]==c[x+2][y-2])
    {
      return -1;
    }
    if(c[x][y]==c[x+1][y] && c[x][y]==c[x+2][y] && c[x][y]==c[x-1][y] && c[x][y]==c[x-2][y])
    {
      return -1;
    }
    if(c[x][y]==c[x][y+1] && c[x][y]==c[x][y-1] && c[x][y]==c[x][y+2] && c[x][y]==c[x][y-2])
    {
      return -1;
    }
  }
  return 0;
}

void out()
{
  for(int i=0; i<20; i++)
  {
    for(int j=0; j<20; j++)
    {
      if(i==0)
      {
        if(j==0)
        {
          cout << "   ";
          continue;
        }
        cout << j;
        if(j/10==0)
        {
          cout << "  ";
        }
        else
        {
          cout << " ";
        }
        continue;
      }
      else if(j==0)
      {
        cout << i;
        if(i/10==0)
        {
          cout << "  ";
        }
        else
        {
          cout << " ";
        }
      }
      if(i-1>riht || i-1<lft || j-1<upp || j-1>dwn)
      {
        cout << "   ";
        continue;
      }
      if(a[i-1][j-1]==1)
      {
        cout << " 1 ";
      }
      else if(a[i-1][j-1]==-1)
      {
        cout << " 0 ";
      }
      else
      {
        cout << "   ";
      }
    }
    cout << endl;
    cout << endl;
  }
  cout << "---------------------------" << endl;
}

void testout()
{
  for(int i=0; i<19; i++)
  {
    for(int j=0; j<19; j++)
    {
      if(b[i][j]==1)
      {
        cout << "1";
      }
      else if(b[i][j]==-1)
      {
        cout << "0";
      }
      else
      {
        cout << " ";
      }
    }
    cout << endl;
  }
}

void randfs(int i,int j,int l,int r,int u,int d)
{
  bool is_now=1;
  int step=0;
  while(true)
  {
    //testout();
    step++;
    int fcnt=-1;
    node2 chosen[1000];
    if(is_now==0)
    {
      node2 pos=three_enemy(b,-1,lcnt,leckb);
      if(pos.x!=-1)
      {
        b[pos.x][pos.y]=1;
        is_now=!is_now;
        continue;
      }
      for(int i=l-1; i<=r+1; i++)
      {
        for(int j=l-1; j<=r+1; j++)
        {
          if(b[i][j]==0)
          {
            chosen[++fcnt].x=i;
            chosen[fcnt].y=j;
          }
        }
      }
      if(fcnt==-1)
      {
        nowbs=1;
        return;
      }
      int ran=rand()%(fcnt+1);
      int x=chosen[ran].x,y=chosen[ran].y;
      node2 tmp;
      tmp.x=x;
      tmp.y=y;
      leckb[++lcnt]=tmp;
      b[x][y]=1;
      if(x==l && x!=0)
      {
        l--;
      }
      if(x==r && x!=18)
      {
        r++;
      }
      if(y==u && u!=0)
      {
        u--;
      }
      if(y==d && d!=18)
      {
        d++;
      }
    }
    else
    {
      node2 pos=three_enemy(b,1,rcnt,leckw);
      if(pos.x!=-1)
      {
        b[pos.x][pos.y]=-1;
        is_now=!is_now;
        continue;
      }
      for(int i=l-1; i<=r+1; i++)
      {
        for(int j=l-1; j<=r+1; j++)
        {
          if(b[i][j]==0)
          {
            chosen[++fcnt].x=i;
            chosen[fcnt].y=j;
          }
        }
      }
      if(fcnt==-1)
      {
        nowbs=1;
        return;
      }
      int ran=rand()%(fcnt+1);
      int x=chosen[ran].x,y=chosen[ran].y;
      node2 tmp;
      tmp.x=x;
      tmp.y=y;
      leckw[++rcnt]=tmp;
      b[x][y]=-1;
      if(x==l && x!=0)
      {
        l--;
      }
      if(x==r && x!=18)
      {
        r++;
      }
      if(y==u && u!=0)
      {
        u--;
      }
      if(y==d && d!=18)
      {
        d++;
      }
    }
    int spm=end(b,leckb,leckw,lcnt,rcnt);
    if(spm!=0)
    {
      if(spm==-1)
      {
        nowbs=0;
        return;
      }
      nowbs=step;
      return;
    }
    is_now=!is_now;
  }
}

void clear()
{
  for(int i=0; i<19; i++)
  {
    for(int j=0; j<19; j++)
    {
      b[i][j]=a[i][j];
    }
  }
  lcnt=cnt;
  rcnt=cnt2;
  for(int i=0; i<190; i++)
  {
    leckb[i]=blck[i];
    leckw[i]=whte[i];
  }
}

void in()
{
  int x,y;
  cout << "press x:";
  cin >> x;
  cout << "press y:";
  cin >> y;
  cout << endl;
  a[x][y]=-1;
  whte[++cnt2].x=x;
  whte[cnt2].y=y;
  if(x==lft && x!=0)
  {
    lft--;
  }
  if(x==riht && x!=18)
  {
    riht++;
  }
  if(y==upp && y!=0)
  {
    upp--;
  }
  if(y==dwn && y!=18)
  {
    dwn++;
  }
}

void clear2()
{
  bs=-114514;
}

void brain()
{
  while(true)
  {
    clear2();
    bool flag=0;
    for(int i=lft; i<=riht; i++)
    {
      for(int j=upp; j<=dwn; j++)
      {
        node2 pl=three_enemy(a,-1,0,whte);
        if(pl.x!=-1)
        {
          best=pl;
          flag=1;
          break;
        }
        if(a[i][j]!=0)
        {
          continue;
        }
        clear();
        b[i][j]=1;
        leckb[++lcnt].x=i;
        leckb[lcnt].y=j;
        //test();
        randfs(i,j,lft,riht,upp,dwn);
        //test();
        node2 as;
        as.x=i;
        as.y=j;
        if(nowbs>bs)
        {
          bs=nowbs;
          best=as;
        }
      }
      if(flag)
      {
        break;
      }
    }
    a[best.x][best.y]=1;
    int x=best.x;
    int y=best.y;
    cnt++;
    blck[cnt]=best;
    if(x==lft && x!=0)
    {
      lft--;
    }
    if(x==riht && x!=18)
    {
      riht++;
    }
    if(y==upp && y!=0)
    {
      upp--;
    }
    if(y==dwn && y!=18)
    {
      dwn++;
    }
    out();
    if(end(a,blck,whte,cnt,cnt2)==1)
    {
      cout << "computer win" << endl;
      break;
    }
    in();
    out();
    if(end(a,blck,whte,cnt,cnt2)==-1)
    {
      cout << "you win" << endl;
      break;
    }
  }
}

int main()
{
  srand(time(0));
  cout << "press any number in the computer to go to the game" << endl;
  cin >> a[0][0];
  cout << "tips:AI's first step is (9,9)" << endl;
  cout << endl;
  a[0][0]=0;
  brain();
  return 0;
}