1 条题解

  • 0
    @ 2025-5-5 11:57:11
    #include <set>
    #include <map>
    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #define LOCAL
    const int MAXL = 20;
    const long long MOD = 1000000007;
    const int MAXK = 10000 + 10;
    const int MAXN = 35000 + 10;
    const int MAXM = 35;
    const int INF = 0x7fffffff;
    using namespace std;
    char str[10][10];
    int tot, X, Y;//代表棋子的数量
    
    void init(){
         tot = 0;
         for (int i = 1; i <= 4; i++){
             scanf("%s", str[i] + 1);
             for (int j = 1; j <= 4; j++) if (str[i][j] != '.') tot++;
         }
         /*for (int i = 1; i <= 4; i++){
             for (int j = 1; j <= 4; j++)
             printf("%c", str[i][j]);
             printf("\n");
         }*/
    }
    //判断是否达成胜利条件
    bool check(int x, int y){
         int num = 0;//判断棋子的个数
         for (int i = 1;i <= 4; i++){
             //注意不要全部判断了
             if (str[x][i] == 'o') num++;
             else if (str[x][i] == 'x') num--;
         }
         if (num == 4 || num == -4) return 1;
         num = 0;
         for (int i = 1; i <= 4; i++){
             if (str[i][y] == 'o') num++;
             else if (str[i][y] == 'x') num--;
         }
         if (num == 4 || num == -4) return 1;
         num = 0;
         //判断主对角线
         for (int i = 1; i <= 4; i++){
             if (str[i][i] == 'o') num++;
             else if (str[i][i] == 'x') num--;
         }
         if (num == 4 || num == -4) return 1;
         num = 0;
         for (int i = 1; i <= 4; i++){
             if (str[i][4 - i + 1] == 'o') num++;
             else if (str[i][4 - i + 1] == 'x') num--;
         }
         if (num == 4 || num == -4) return 1;
         return 0;
    }
    int MaxSearch(int x, int y, int alpha);
    int MinSearch(int x, int y, int beta);
    
    int MaxSearch(int x, int y, int alpha){
        int Ans = -INF;
        //最大获益
        if (check(x, y)) return Ans;
        if (tot == 16) return 0;
    
        for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++){
            if (str[i][j] != '.') continue;
            str[i][j] = 'x';tot++;
            int tmp = MinSearch(i, j, Ans);
            str[i][j] = '.';tot--;
            Ans = max(Ans, tmp);
            if (Ans >= alpha) return Ans;
        }
        return Ans;
    }
    int MinSearch(int x, int y, int beta){
        int Ans = INF;
        //最小损失
        if (check(x, y)) return Ans;
        if (tot == 16) return 0;//平局
    
        for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++){
            if (str[i][j] != '.') continue;
            str[i][j] = 'o'; tot++;
            int tmp = MaxSearch(i, j, Ans);
            str[i][j] = '.'; tot--;
            Ans = min(Ans , tmp);
            if (Ans <= beta) return Ans;
        }
        return Ans;
    }
    bool dfs(){
         int beta = -INF;
         for (int i = 1; i <= 4; i++)
         for (int j = 1; j <= 4; j++){
             if (str[i][j] != '.') continue;
             str[i][j] = 'x'; tot++;
             int tmp = MinSearch(i, j, beta);
             str[i][j] = '.'; tot--;
             beta = max(beta, tmp);
             if (beta == INF){
                X = i;Y = j;
                return 1;
             }
         }
         return 0;
    }
    
    int main () {
    
        char ch[2];
        while (scanf("%s", ch)!= EOF && ch[0] != '$'){
              init();
              if (dfs()) printf("(%d,%d)\n", X - 1, Y - 1);//代表终点坐标
              else printf("#####\n");
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    569
    时间
    3000ms
    内存
    32MiB
    难度
    6
    标签
    递交数
    12
    已通过
    1
    上传者