题解 P4363 【[九省联考2018]一双木棋chess】

2018-04-09 08:55:42


这是一份暴力题解。

Prelude

这个题当时在考场上马上就想到了Minimax搜索,然后带上AlphaBeta剪枝就可以乱搞了,一个小时连码带对拍搞完,然后开始睡觉干后面题的暴力

考试结束前5分钟我把题意看错了,慌得要命,改了之后样例输出3,交卷之前一分钟,潜意识中感到不对,连着按了30几下Ctrl-Z,撤回到了正确的版本,编译了一下,连样例都没测,就交卷了。还好rp好,没有WA声一片,还混了75= =

出场后和 @Anoxiacxy 分析了一下,发现似乎可以压轮廓线?考试的时候果然智商下线啊……

后来听说我省(HB)一个初三的dalao(就楼下那位)当场码出正解,无限膜拜orzorzorz

解法

这种 $n, m \le 10$ 的题,一看就是要暴力。但是直接暴力 + AlphaBeta剪枝 + 节点排序只能拿到70.

考虑直接爆搜+优化。如果每个状态中记录整个棋盘,每次扩展就要遍历整个棋盘找合适的点。考虑优化这个过程。

我们知道,如果按照题目的要求摆放,棋子一定构成包含棋盘左上角的一个连通块。由于我特别弱,不会轮廓线状压DP,就考虑只在状态中记录每行每列的最后一个棋子的位置(显然,已经摆放的棋子是谁的,对于状态的转移没有影响)。

棋子只会越来越多,所以构成一个DAG。打大暴力后发现有很多的重复状态,所以记忆化应该有用。每个状态里面有 $n+m$ 个数字,直接记录显然药丸,于是我们hash一下(其中pair记录的是状态-当前玩家):

namespace std {
    template<>
    struct hash<State> {
        size_t operator()(const State& s) const {
            size_t h = 0, base = 131;
            for(register int i = 1; i <= n; i++, base *= 13) 
                h += s.row[i] * base; // BKDRHash
            return h;
        }
    };
    template<typename T1, typename T2>
    struct hash<pair<T1, T2> > {
        size_t operator()(const pair<T1, T2>& s) const {
            size_t h = 0;
            h = std::hash<T1>()(s.first) ^ std::hash<T2>()(s.second);
            return h;
        }
    };
}

这样就可以上 unordered_map 了。用unordered_map记忆化之后最后一个点就可以跑过了,而且也不慢。

代码

/*
    暴力+hash_map
*/
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> Step;

const int MAXN = 10, INF = 0x3f3f3f3f;
int n, m, A[MAXN+10][MAXN+10], B[MAXN+10][MAXN+10];

struct State {
    int row[MAXN+10], col[MAXN+10];
    State() {
        memset(row, 0, sizeof(row)); 
        memset(col, 0, sizeof(col));
    }
    bool full() {
        for(int i = 1; i <= n; i++)
            if(row[i] != m) return false;
        return true;
    }
    bool possible(int x, int y) {
        return row[x] == y-1 && col[y] == x-1;
    }
    bool operator==(const State &rhs) const {
        for(int i = 1; i <= n; i++)
            if(row[i] != rhs.row[i]) return false;
        return true;
    }
    const State& operator=(const State &rhs) {
        memcpy(row, rhs.row, sizeof(row));
        memcpy(col, rhs.col, sizeof(col));
        return (const State&) *this;
    }
} S;

namespace std {
    template<>
    struct hash<State> {
        size_t operator()(const State& s) const {
            size_t h = 0, base = 131;
            for(register int i = 1; i <= n; i++, base *= 13) 
                h += s.row[i] * base;
            return h;
        }
    };
    template<typename T1, typename T2>
    struct hash<pair<T1, T2> > {
        size_t operator()(const pair<T1, T2>& s) const {
            size_t h = 0;
            h = std::hash<T1>()(s.first) ^ std::hash<T2>()(s.second);
            return h;
        }
    };
}

unordered_map<pair<State, int>, int > cache;

void init() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &A[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &B[i][j]);
}

int Minimax(State &u, int player) {

    if(u.full()) return 0;

    if(cache.count({u, player}))
        return cache[{u, player}];

    int sz = 0; Step step[(MAXN+1) * 2];
    if(player == 1) {   //Max 玩家
        int maxv = -INF;
        for(int i = 1; i <= n; i++) if(u.row[i] < m && u.possible(i, u.row[i]+1))
            step[++sz] = { A[i][u.row[i]+1], {i, u.row[i]+1} };
        for(int i = 1; i <= sz; i++) {
            u.row[step[i].snd.fst]++; u.col[step[i].snd.snd]++;
            maxv = max(maxv, step[i].fst + Minimax(u, 3 - player));
            u.row[step[i].snd.fst]--; u.col[step[i].snd.snd]--;
        }
        cache[{u, player}] = maxv;
        return maxv;
    } else {    // Min 玩家
        int minv = INF;
        for(int i = 1; i <= n; i++) if(u.row[i] < m && u.possible(i, u.row[i]+1))
            step[++sz] = { -B[i][u.row[i]+1], {i, u.row[i]+1} };
        for(int i = 1; i <= sz; i++) {
            u.row[step[i].snd.fst]++; u.col[step[i].snd.snd]++;
            minv = min(minv, step[i].fst + Minimax(u, 3 - player));
            u.row[step[i].snd.fst]--; u.col[step[i].snd.snd]--;
        }
        cache[{u, player}] = minv;
        return minv;
    }
}

void work() {
    printf("%d", Minimax(S, 1));
}

int main() {
    init(); work();
    return 0;
}