3106: [cqoi2013]棋盘游戏

链接

分析：

　　极大极小搜索 + 记忆化。

代码

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long LL; const int INF = 1e9;
 int f[][][][][][];
 int dx[] = {,,,-,,,,-};
 int dy[] = {,-,,,,-,,};
 int n; int Minimax(int player,int step,int a,int b,int c,int d) {
     if (step > n*) return INF;
     if (a==c && b==d) {
         if (player) return INF;
         return ;
     }
     if (f[player][step][a][b][c][d]) return f[player][step][a][b][c][d];
     int res = ,x = ,y = ;
     if (player) { // 黑棋走
         res = INF;
         for (int i=; i<; ++i) {
             x = c + dx[i], y = d + dy[i];
             if (x>= && x<=n && y>= && y<=n) res = min(res,Minimax(player^,step+,a,b,x,y));
         }
     }
     else { // 白棋走
         for (int i=; i<; ++i) {
             x = a + dx[i], y = b + dy[i];
             if (x>= && x<=n && y>= && y<=n) res = max(res,Minimax(player^,step+,x,y,c,d));
         }
     }
     res ++;
     f[player][step][a][b][c][d] = res;
     return res;
 } int main() {
     int a,b,c,d;
     cin >> n >> a >> b >> c >> d;
     if (abs(a-c)+abs(b-d) == ) puts("WHITE 1"); // 白子一步吃掉黑子
     else printf("BLACK %d",Minimax(,,a,b,c,d));
     return ;
 }