题解 P4363 【[九省联考2018]一双木棋chess】
panda_2134
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记录的是状态-当前玩家）：
```cpp
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`记忆化之后最后一个点就可以跑过了，而且也不慢。
## 代码
```cpp
/*
暴力+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;
}
```