poj1568 Find the Winning Move----Find the Winning Move极大极小搜索(二)

2014-11-24 10:18:18 · 作者: · 浏览: 1
) return maxi;
if (chess==16) return 0;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
if (state[i][j]=='.') {
state[i][j]='x';
chess++;
tmp = minfind(i,j,maxi);
chess--;
state[i][j]='.';
maxi = max(maxi, tmp);
if (maxi>=mini) return maxi;// f(p)正无穷,先手必胜
}
return maxi;
}
int minfind(int x,int y,int maxi) {
int tmp, mini = inf;
if (over(x,y)) return mini;
if (chess==16) return 0;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
if (state[i][j]=='.') {
state[i][j]='o';
chess++;
tmp = maxfind(i,j,mini);
chess--;
state[i][j]='.';
mini = min(mini, tmp);
if (mini<=maxi) return mini;//f(p)负无穷,后手必胜
}
return mini;
}
bool tryit() {
int tmp, maxi = -inf;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
if (state[i][j]=='.') {
state[i][j] = 'x';
chess++;
tmp = minfind(i,j,maxi);
chess--;
state[i][j] = '.';
if (tmp>=maxi) {
maxi = tmp;
xi = i; xj = j;
}
if (maxi==inf) return true;//f(p)正无穷,先手必胜
}
return false;
}
int main() {
while (scanf("%c",&ch)) {
if (ch=='$') break;
scanf("%c",&ch);

chess = -4;
for (int i=0;i<4;i++)
for (int j=0;j<5;j++) {
scanf("%c",&state[i][j]);
chess += state[i][j]!='.';
}
if (chess<=4) { //强力剪枝
printf("#####\n");
continue;
}
if (tryit()) printf("(%d,%d)\n",xi,xj);
else printf("#####\n");
}
return 0;
}