P8658求调,40分剩下的全部TLE
  • 板块学术版
  • 楼主Tarkin
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/3 17:57
  • 上次更新2024/12/3 20:55:03
查看原帖
P8658求调,40分剩下的全部TLE
385150
Tarkin楼主2024/12/3 17:57
#include <bits/stdc++.h>
using namespace std;
map<pair<string, bool>, int> memory;
int dfs(string board, bool isMyTurn) {
    if (memory.count({ board,isMyTurn })) {
        return memory[{ board, isMyTurn }];
    }
    if (board.find("LOL") != string::npos) {
        if (isMyTurn) {
            return memory[{ board, isMyTurn }] = -1;
        }
        else {
            return memory[{ board, isMyTurn }] = 1;
        }
    }
    if (board.find('*') == string::npos) {
        return memory[{ board, isMyTurn }] = 0;
    }
    int result = 0;
    if (isMyTurn) {
        result = -1;
    }
    else {
        result = 1;
    }
    for (int i = 0; i < board.size(); i++) {
        if (board[i] == '*') {
            for (char c : {'L', 'O'}) {
                board[i] = c;
                int subResult = dfs(board, !isMyTurn);
                board[i] = '*';
                if (isMyTurn) {
                    if (subResult == 1) {
                        result = 1;
                        break;
                    }
                    if (subResult == 0) {
                        result = max(result, 0);
                    }
                }
                else {
                    if (subResult == -1) {
                        result = -1;
                        break;
                    }
                    if (subResult == 0) {
                        result = min(result, 0);
                    }
                }
            }
        }
    }
    return memory[{ board, isMyTurn }] = result;
}
int main() {
    int n = 0;
    string board;
    cin >> n;
    while (n--) {
        cin >> board;
        memory.clear();
        if (board.size() < 3) {
            cout << 0 << endl;
            continue;
        }
        cout << dfs(board, true) << endl;
    }
    return 0;
}
2024/12/3 17:57
加载中...