#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;}else 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*** W"
"elcome to the game of Connect! ***\n\nBy Keith Pomakis (pomakis@pobox.com)\nA"
"pril, 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;c++)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 thinking.":"Thinking.",W[B]);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 dropped its",W[B]);j(" piece into colum"
"n %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;}