求助插头DP
查看原帖
求助插头DP
448887
cancan123456楼主2022/3/6 19:53
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2 << 24;
typedef long long ll;
const ll mod = 1919810;
char gird[13][13];
ll pow[14];
int head[mod];
int key[2][N];
ll val[2][N];
int next[N];
int cnt[2];
int now;
void add(int k, ll v) {
	int t = head[k % mod];
	for (; t != 0; t = next[t]) {
		if (key[now][t] == k) {
			val[now][t] += v;
			return;
		}
	}
	cnt[now]++;
	t = cnt[now];
	key[now][t] = k;
	val[now][t] = v;
	next[t] = head[k % mod];
	head[k % mod] = t;
}
char read_char() {
	char c;
	do {
		c = getchar();
	} while (c != '*' && c != '.');
	return c;
}
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			gird[i][j] = read_char();
		}
	}
	int ansx = -1, ansy = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (gird[i][j] == '.') {
				ansx = i;
				ansy = j;
			}
		}
	}
	for (int i = 0; i <= 13; i++) {
		pow[i] = 1 << (2 * i);
	}
	ll ans = 0;
	now = 0;
	add(0, 1);
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= cnt[now]; j++) {
			key[now][j] <<= 2;
		}
		for (int j = 0; j < n; j++) {
			int last = now;
			now ^= 1;
			memset(head, 0, sizeof head);
			cnt[now] = 0;
			for (int k = 1; k <= cnt[last]; k++) {
				int bit = key[last][k];
				ll num = val[last][k];
				int b1 = (bit >> (j * 2)) & 3;
				int b2 = (bit >> ((j + 1) * 2)) & 3;
				if (gird[i][j] == '*') {
					if (b1 == 0 && b2 == 0) {
						add(bit, num);
					}
				} else if (b1 == 0 && b2 == 0) {
					if (gird[i][j + 1] == '.' && gird[i + 1][j] == '.') {
						add(bit + pow[j] + pow[j + 1] * 2, num);
					}
				} else if (b1 == 0 && b2 != 0) {
					if (gird[i][j + 1] == '.') {
						add(bit, num);
					}
					if (gird[i + 1][j] == '.') {
						add(bit - pow[j + 1] * b2 + pow[j] * b2, num);
					}
				} else if (b1 != 0 && b2 == 0) {
					if (gird[i][j + 1] == '.') {
						add(bit - pow[j] * b1 + pow[j + 1] * b1, num);
					}
					if (gird[i + 1][j] == '.') {
						add(bit, num);
					}
				} else if (b1 == 1 && b2 == 1) {
					ll top = 0;
					for (int l = j + 1; l < m; l++) {
						if (((bit >> (l * 2)) & 3) == 1) {
							top++;
						}
						if (((bit >> (l * 2)) & 3) == 2) {
							top--;
						}
						if (top == 0) {
							add(bit - pow[j] - pow[j + 1] - pow[l], num);
							break;
						}
					}
				} else if (b1 == 2 && b2 == 2) {
					ll top = 0;
					for (int l = j; l >= 0; l--) {
						if (((bit >> (l * 2)) & 3) == 1) {
							top++;
						}
						if (((bit >> (l * 2)) & 3) == 2) {
							top--;
						}
						if (top == 0) {
							add(bit - pow[j] * 2 - pow[j + 1] * 2 + pow[l], num);
							break;
						}
					}
				} else if (b1 == 2 && b2 == 1) {
					add(bit - pow[j] * 2 - pow[j + 1],num);
				} else if (i == ansx && j == ansy) {
					ans += num;
				}
			}
		}
	}
	printf("%lld", ans);
	return 0;
}

#3 WA掉(输出 0)

#8 RE

2022/3/6 19:53
加载中...