提供一个封装的链表版哈希表代码。
方便对多维数组开多个哈希表,以及对单个状态存多个信息。
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int N = 50000, M = 100007;
const int offset = 2, mask = 3;
int n, m, ex, ey;
int g[20][20];
struct Hash_Table {
int h[M], ne[N], idx;
int state[N];
i64 val[N];
void init() { idx = 0, memset(h, -1, sizeof h); }
void roll() { for (int i = 0; i < idx; i++) state[i] <<= offset; }
void push(int s, i64 w) {
int x = s % M;
for (int i = h[x]; ~i; i = ne[i])
if (state[i] == s)
return val[i] += w, void();
state[idx] = s, val[idx] = w;
ne[idx] = h[x], h[x] = idx++;
}
} h[2], *h0, *h1;
int get(int s, int k) { return s >> (k * offset) & mask; }
int set(int k, int v) { return v * (1 << (k * offset)); }
void add(int s, i64 w) { h1->push(s, w); }
int find1(int s, int j) {
for (int u = j - 2, c = 1; ; u--) {
int z = get(s, u);
if (z == 2) c++;
if (z == 1 && !--c) return u;
}
}
int find2(int s, int j) {
for (int u = j + 1, c = 1; ; u++) {
int z = get(s, u);
if (z == 1) c++;
if (z == 2 && !--c) return u;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
if (c == '.') {
g[i][j] = 1;
ex = i, ey = j;
}
}
}
h0 = h, h1 = h + 1;
h1->init();
add(0, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
swap(h0, h1);
h1->init();
for (int k = 0; k < h0->idx; k++) {
int s = h0->state[k];
i64 w = h0->val[k];
int x = get(s, j - 1), y = get(s, j);
bool r = g[i][j + 1], d = g[i + 1][j];
if (!g[i][j]) {
if (!x && !y) add(s, w);
continue;
}
if (!x && !y && r && d) add(s + set(j - 1, 1) + set(j, 2), w);
if (!x && y) {
if (r) add(s, w);
if (d) add(s + set(j - 1, y) - set(j, y), w);
}
if (x && !y) {
if (r) add(s - set(j - 1, x) + set(j, x), w);
if (d) add(s, w);
}
if (x == 1 && y == 1)
add(s - set(j - 1, x) - set(j, y) - set(find2(s, j), 1), w);
if (x == 2 && y == 2)
add(s - set(j - 1, x) - set(j, y) + set(find1(s, j), 1), w);
if (x == 2 && y == 1) add(s - set(j - 1, x) - set(j, y), w);
if (i == ex && j == ey) add(0, w);
}
}
h1->roll();
}
cout << (h1->idx ? h1->val[0] : 0);
return 0;
}