1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
using namespace std;
const int NPLAYERS=2;
const int WID=8,HEI=9;
template <typename T>
ostream& operator<<(ostream &os,const vector<T> &v){
const int sz=v.size();
if(sz==0)return os;
os<<v[0];
for(int i=1;i<sz;i++)os<<' '<<v[i];
return os;
}
struct Move{
int x,y;
Move(void):x(-1),y(-1){}
Move(int idx):x(idx%WID),y(idx/WID){}
Move(int _x,int _y):x(_x),y(_y){}
int idx(void){return WID*y+x;}
};
class Board{
int balls[WID*HEI],colour[WID*HEI];
int wonby=-1; //kept up-to-date by stabilise()
int nballs=0;
public:
inline Board(void){
memset(balls,0,WID*HEI*sizeof(int));
memset(colour,0,WID*HEI*sizeof(int));
}
inline Board(const Board &other):wonby(other.wonby){
memcpy(balls,other.balls,WID*HEI*sizeof(int));
memcpy(colour,other.colour,WID*HEI*sizeof(int));
}
inline int getballs(int idx){return balls[idx];}
inline int getballs(int x,int y){return getballs(WID*y+x);}
inline int getcolour(int idx){return colour[idx];}
inline int getcolour(int x,int y){return getcolour(WID*y+x);}
inline bool put(int x,int y,int c){
const int idx=WID*y+x;
if(balls[idx]&&colour[idx]!=c)return false;
balls[idx]++;
colour[idx]=c;
nballs++;
stabilise();
return true;
}
inline bool put(int idx,int c){return put(idx%WID,idx/WID,c);}
inline bool putq(int idx,int c) const{return !balls[idx]||colour[idx]==c;}
inline bool putq(int x,int y,int c) const{return putq(WID*y+x,c);}
inline void stabilise(void){
int nballs[WID*HEI],ncolour[WID*HEI]; //new values
bool changed;
int x,y;
do {
changed=false;
memcpy(nballs,balls,WID*HEI*sizeof(int));
memcpy(ncolour,colour,WID*HEI*sizeof(int));
for(y=0;y<HEI;y++)for(x=0;x<WID;x++){
const int idx=WID*y+x;
const int nnei=(y>0)+(x>0)+(y<HEI-1)+(x<WID-1);
if(balls[idx]>=nnei){
const int quo=balls[idx]/nnei;
nballs[idx]-=nnei*quo;
if(y>0){nballs[idx-WID]+=quo;ncolour[idx-WID]=colour[idx];}
if(x>0){nballs[idx-1]+=quo;ncolour[idx-1]=colour[idx];}
if(y<HEI-1){nballs[idx+WID]+=quo;ncolour[idx+WID]=colour[idx];}
if(x<WID-1){nballs[idx+1]+=quo;ncolour[idx+1]=colour[idx];}
changed=true;
}
}
wonby=-1;
for(int i=0;i<WID*HEI;i++){
if(nballs[i]==0)continue;
if(wonby==-1)wonby=ncolour[i];
else if(wonby!=ncolour[i]){
wonby=-1;
break;
}
}
memcpy(balls,nballs,WID*HEI*sizeof(int));
memcpy(colour,ncolour,WID*HEI*sizeof(int));
} while(changed&&wonby==-1);
}
//returns -1 for no win yet, >=0 for that colour
inline int checkwin(void) const{return wonby;}
inline int ballcount(int c) const{
int i,count=0;
for(i=0;i<WID*HEI;i++){
count+=balls[i]*(colour[i]==c);
}
return count;
}
inline int totalballcount(void) const{return nballs;}
void print(ostream &os){
int x,y;
for(y=0;y<HEI;y++){
for(x=0;x<WID;x++){
if(balls[WID*y+x]){
os<<"\x1B[3"<<colour[WID*y+x]+1<<'m'<<setw(2)<<balls[WID*y+x]<<"\x1B[0m ";
} else os<<".. ";
}
os<<endl;
}
}
};
Move randommove(const Board &bd,int c){
Move poss[WID*HEI];
int nposs=0;
int i;
for(i=0;i<WID*HEI;i++){
if(bd.putq(i,c)){
poss[nposs].x=i%WID;
poss[nposs].y=i/WID;
nposs++;
}
}
if(nposs==0)return Move();
return poss[rand()%nposs];
}
|
