第三题

#include<iostream>
int play[3][3] = {0};
int score[3][3];

bool check_row(int i, int role) {
    if (play[i][0] != role) return false;
    if (play[i][1] != role) return false;
    if (play[i][2] != role) return false;
    return true;
}

bool check_col(int j, int role) {
    if (play[0][j] != role) return false;
    if (play[1][j] != role) return false;
    if (play[2][j] != role) return false;
    return true;
}

bool check_diag(int role) {
    if (play[1][1] != role) return false;
    if (play[0][0] == role && play[2][2] == role) return true;
    if (play[0][2] == role && play[2][0] == role) return true;
    return false;
}

bool check(int i, int j, int role) {
    return check_row(i, role) || check_col(j, role) || check_diag(role);
}

int adv(int step) {
    if (step == 9) return 0;
    int role = (step % 2) + 1;
    const int inf = 1000000000;
    int best = -inf;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (play[i][j] == 0) {
                play[i][j] = role;
                if (check(i, j, role)) {
                    best = inf;
                }
                else {
                    int test = score[i][j] - adv(step + 1);
                    if (best < test) {
                        best = test;
                    }
                }
                play[i][j] = 0;
            }
        }
    }
    return best;
}

int main() {
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            std::cin >> score[i][j];
    int d = adv(0);
    if (d > 0)
        std::cout << "First Win\n";
    else
        std::cout << "Second Win\n";
}

该程序主要使用了（ ）算法思想。

{{ select(1) }}

• 分治
• 贪心
• 动态规划
• 回溯