#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#define m(a,b)=malloc(a*sizeof(b))
#define j printf(
#define x for(
#define t else
typedef int q;typedef char b;typedef struct{b**g;q*(n[2]);q z[2];q o;q l;}r;q
_,_,w,C,y,G,o,g,***s,z,e,p=1,*T,f[2],R[2],B,l,S,L,c,H,D,O,*i;clock_t A=5e5,U;r
n[21],*P=n;b K[9],F[2],J[2];q k(q f,q c){q H=0,C=0,O,G=0,e=0,**o=P->n;x;P->g[c
][H]-2&&++H<w;);if(H-w){x P->g[c][H]=f,P->l++;s[c][H][C]+1;)G+=o[f][O=s[c][H][C
++]],e+=o[f^1][O],o[f][O]<<=1,o[f^1][O]=0,(o[f][O]==z&&P->o==2)&&(P->o=f);P->z[
f]+=G;P->z[f^1]-=e;}t H=-1;return H;}void a(void){q L=0,U=g*sizeof(1);r*i;P=(i=
n+e++)+1;if(e==p){x P->g m(_,b*);L<_;)P->g[L++]m(w,b);*P->n m(g,1);P->n[1]m(g,1
);p++;}x L=0;L<_;L++)memcpy(P->g[L],i->g[L],w);memcpy(*P->n,*i->n,U);memcpy(P->
n[1],i->n[1],U);*P->z=*i->z;P->z[1]=i->z[1];P->o=i->o;P->l=i->l;}q d(q f,q R,q
V,q M){q c,z,D;U<=clock()&&(U+=A,j"."),fflush(stdout));if(P->o-2)D=P->o-f?3e4-e
:e-3e4;t if(P->l==y)D=0;t if(R-e){D=-3e4;x c=0;c<_;c++)if(P->g[T[c]][w-1]==2){a
();k(f^1,T[c]);if((z=d(f^1,R,-M,-V))>D){D=z;if(D>V)V=D;}P=&n[--e];if(D>M)break;
}}t D=P->z[f^1]-P->z[f];return-D;}q W[]={'X','O'};void h(void){if(!fgets(K,9,
stdin)||*K=='q')j"\nGoodbye!\n"),exit(0);}q v(b*p,q y,q T,q D){q c=-1,U=1;x;!U
||(U-EOF&&(c<y||c>T));U=sscanf(K,"%d",&c)){D-5||j"Skill level of ");j D+1?"%s "
"[%d]? ":"%s? ",p,D);h();}return U-EOF?c:D;}void u(void){q S,l=w-1;j"\n");x;l>=
0;l--){j"|");x S=0;S<_;S++)(P->g[S][l]-2&&j"%s%c%s|",F,W[(q)P->g[S][l]],F))||j
"%s %s|",F,F);j"\n+");x;S--;)j"%s-%s+",J,J);j"\n");}j" ");x S=0;S<_;S++)j"%s%d"
"%s ",F,S>8?(S+1)/10:S+1,F);if(_>9){j"\n ");x S=0;S<_;S++)j"%s%c%s ",F,S>8?'0'+
(S+1)-((S+1)/10)*10:' ',F);}j"\n\n");}q main(){j"\n*** Welcome to the game of "
"Connect! ***\n\nBy Keith Pomakis (pomakis@pobox.com)\nApril, 2005\n\n");_=v(
"Width of board",1,40,7);w=v("Height of board",1,40,6);o=v("Number to connect",
1,40,4);_<20&&(*F=' ',*J='-');if(!(l=v("Number of human players (0, 1 or 2)",0,
2,1)))*R=v("player X",1,20,5),R[*f=f[1]=1]=v("player O",1,20,5);t if(l==1){R[f[
1]=1]=v("computer",1,20,5);do{j"Would you like to go first [y]? ");h();}while((
*K=tolower(*K))-'y'&&*K-'n'&&*K-'\n');B=*K=='n';}y=_*w;z=1<<o;g=_<o&&w<o?0:(_<o
?_*(w-o+1):(w<o?w*(_-o+1):(4*_*w-3*_*o-3*w*o+3*_+3*w-4*o+2*o*o+2)));srand(time(
0));P->g m(_,b*);x;C<_;C++){P->g[C]m(w,b);x c=0;c<w;)P->g[C][c++]=2;}*P->n m(g,
1);P->n[1]m(g,1);x C=0;C<g;C++)P->n[0][C]=P->n[1][C]=1;*P->z=P->z[1]=g;P->o=2;s
m(_,q**);x C=0;C<_;C++)x s[C]m(w,q*),c=0;c<w;)s[C][c]m((o*4+1),1),*s[C][c++]=-1
;x C=0;C<w;C++)x c=0;c<_-o+1;c++,O++)x L=0;L<o;L++){i=s[c+L][C];x H=0;i[H]+1;H
++);i[H++]=O;i[H]=-1;}x C=0;C<_;C++)x c=0;c<w-o+1;c++,O++)x L=0;L<o;L++){i=s[C]
[c+L];x H=0;i[H]+1;H++);i[H++]=O;i[H]=-1;}x C=0;C<w-o+1;C++)x c=0;c<_-o+1;c++,O
++)x L=0;L<o;L++){i=s[c+L][C+L];x H=0;i[H]+1;H++);i[H++]=O;i[H]=-1;}x C=0;C<w-o
+1;C++)x c=_-1;c>=o-1;c--,O++)x L=0;L<o;L++){i=s[c-L][C+L];x H=0;i[H]+1;H++);i[
H++]=O;i[H]=-1;}T m(_,1);G=(_-1)/2;x C=1;C<=_;C++)T[C-1]=G,G+=C%2?C:-C;x;P->o==
2&&P->l-y;B=!B){u();if(!f[B])do l-2||j"Player %c, ",W[B]);while((S=v("Drop in "
"which column",1,_,-1)-1)<0||k(B,S)<0);t{q X=0,N=-3e4,Z=0;j l-1?"Player %c is "
"t":"T",W[B]);j"hinking.");fflush(stdout);if(P->l<2&&_==7&&w==6&&o==4&&(!P->l||
*P->g[3]-2))S=3;t x S=-1,c=0;c<_;c++,P=n+--e){a();if(k(B,H=T[c])+1){if(P->o-B)U
=clock()+A,X=d(B,R[B],-3e4,-N);t{S=H;P=n+--e;break;}if(X>N)N=X,S=H,Z=1;t if(X
==N&&!((rand()>>4)%++Z))S=H;}}k(B,S);j l?"\n\nI dropped my":"\n\nPlayer %c dro"
"pped its",W[B]);j" piece into column %d.\n",S+1);}}u();if(P->o-2){x;P->n[P->o]
[D]-z;)D++;x L=0;L<w;L++)x C=0;C<_;C++)x B=0;s[C][L][B]+1;)if(s[C][L][B++]==D)
goto Q;Q:x H=w-1;H>=0;H--)x c=_-1;c>=0;c--)x B=0;s[c][H][B]+1;)if(s[c][H][B++]
==D)goto I;I:(P->o&&j l-1?"Player %c":"I",W[1]))||j l-1?"Player %c":"You",*W);j
" won!  (%d,%d) to (%d,%d)\n\n",C+1,L+1,c+1,H+1);}t j"There was a tie!\n\n");
return 0;}