2018-04-09 08:55:42

## 解法

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;
}
};
}

## 代码

/*
暴力+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;
}
• star
首页