fork download 
  1. #include <cstdio>
  2. #include <cstdlib>
  3.  
  4. using namespace std;
  5.  
  6. int n, m;
  7. int a[21][2];
  8. int re[(1<<16)+5][21];
  9. bool sign[(1<<16)+5][21];
  10.  
  11. int f(int mask, int last){
  12.     if(mask==(1<<(n*n))-1) return 2;
  13.     if(sign[mask][last]) return re[mask][last];
  14.     re[mask][last]= 1; bool draw= false;
  15.     if(last>m){
  16.         for(int i=1;i<=m;i++){
  17.             if((mask&(1<<(i-1)))==0 && abs(a[i][0]-a[last][0])+abs(a[i][1]-a[last][1])!=1){
  18.                 if(f(mask|(1<<(i-1)),i)==2) draw= true;
  19.                 else re[mask][last]&= f(mask|(1<<(i-1)),i);
  20.             }
  21.         }
  22.     }
  23.     else{
  24.         for(int i=m+1;i<=n*n;i++){
  25.             if((mask&(1<<(i-1)))==0 && abs(a[i][0]-a[last][0])+abs(a[i][1]-a[last][1])!=1){
  26.                 if(f(mask|(1<<(i-1)),i)==2) draw= true;
  27.                 else re[mask][last]&= f(mask|(1<<(i-1)),i);
  28.             }
  29.         }
  30.     }
  31.     re[mask][last]= 1- re[mask][last];
  32.     if(re[mask][last]==0 && draw==true) re[mask][last]= 2;
  33.     sign[mask][last]= true; return re[mask][last];
  34. }
  35.  
  36. int main(){
  37.     scanf("%d", &n);
  38.     int cnt= 0;
  39.     for(int k=0;k<=1;k++){
  40.         for(int i=1;i<=n;i++){
  41.             for(int j=1;j<=n;j++){
  42.                 if((i+j)%2==k){
  43.                     cnt++; a[cnt][0]= i; a[cnt][1]= j;
  44.                     if(k==0) m++;
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     a[n*n+1][0]= 1000000005; a[n*n+1][1]= 1000000005;
  50.     int res= f(0,n*n+1);
  51.     if(res==0) printf("Second player win\n");
  52.     if(res==1) printf("First player win\n");
  53.     if(res==2) printf("DRAW\n");
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0s 9824KB
comments (?)
stdin 
Standard input is empty
stdout 
DRAW
https://ideone.com/vChQfK
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!