[NOIP2018 TG D2T2]填数游戏

题目大意：$NOIP2018\;TG\;D2T2$

题解：在skip2004的博客基础上修改的，也是暴搜。

说明一下把vector改成数组并不可以通过此题，记录。

结论：在$m>n+1$时答案为$3(n,m)$（$(n,m)$表示长$m$高$n$的矩形的答案）

发现其中判断右下角矩阵斜线全相等的部分可以优化，因为对于一条斜线，每次都搜右下角的矩阵，有很多部分都是重复搜的，完全可以每次搜只与它下面的一层比较，发现一条斜线中最多只有一个$01$交界处，于是对于这一行进行特判，少搜一个，但是注意最下面的一行可能不是底，需要把整个矩阵搜一遍。

这样似乎复杂度是不变的（我数学差），然后交了一下，发现还是会$TLE$，到洛谷$IDE$上测了一下是$1126ms$，于是加上一堆$register$和$const$就过了，最慢的点$925ms$。

我在洛谷$IDE$上又试了一下，原来全部搜一遍的代码加上$register$和$const$用时是$1263ms$（所有测试数据均为 8 9 ）

卡点：$TLE$

 

C++ Code：

#include <cstdio>
#include <algorithm>
#define maxn 10
const int mod = 1e9 + 7;
inline int pw(int base, int p) {
	if (p < 0) return 1;
	int res = 1;
	for (; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
	return res;
}
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}

int n, m, ans;
int s[maxn][maxn];
struct node {
	int x, y;
	inline node() {};
	inline node(int __x, int __y) {x = __x, y = __y;}
} v[maxn << 1][maxn];
int tot[maxn << 1];

void dfs(const int X) {
	if (X < 2) {
		ans++;
		return ;
	}
	for (register node *i = v[X + 1]; i -> x; i++) {
		const int x = i -> x, y = i -> y;
		if (1 < x && x < n && y < m) {
			if (x == X) {
				if (s[x][y] == s[x - 1][y + 1]) {
					for (register int j = x; j < n; j++) {
						for (register int k = y + 2; k <= m; k++) if (s[j][k] != s[j + 1][k - 1]) return ;
					}
				} else if (x != 2) {
					for (register int j = x; j < n; j++) {
						for (register int k = y + 3; k <= m; k++) if (s[j][k] != s[j + 1][k - 1]) return ;
					}
				}
			} else {
				if (s[x][y] == s[x - 1][y + 1]) {
					for (register int j = y + 2; j <= m; j++) if (s[x][j] != s[x + 1][j - 1]) return ;
				} else if (x != 2) {
					for (register int j = y + 3; j <= m; j++) if (s[x][j] != s[x + 1][j - 1]) return ;
				}
			}
		}
	}
	for (register node *i = v[X]; i -> x; i++) s[i -> x][i -> y] = 1;
	dfs(X - 1);
	for (register node *i = v[X]; i -> x; i++) {
		s[i -> x][i -> y] = 0;
		dfs(X - 1);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	if (n > m) std::swap(n, m);
	if (n == 1) {
		printf("%d\n", pw(2, m));
		return 0;
	}
	int res = pw(3, m - n - 1);
	m = min(n + 1, m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) v[i + j][tot[i + j]++] = node(i, j);
	}
	dfs(n + m);
	printf("%lld\n", static_cast<long long> (ans) * res % mod);
	return 0;
}