比赛 2025.12.6 评测结果 WWWWEEEEEEEEETTAEEEE
题目名称 填数游戏 最终得分 5
用户昵称 彭欣越 运行时间 4.443 s
代码语言 C++ 内存使用 3.44 MiB
提交时间 2025-12-06 12:27:57
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[10][10],dp[10][10],mi,flag;
void dfs (int x,int y,int w,int id) {
	if (x==n&&y==m) {
		if (mi<w) {
		    flag=1;
			return;
		}
		mi=min(mi,w);
	}
	if (flag) return;
	if (y<m) {
		if (a[x][y+1]) dfs(x,y+1,w+(1<<id),id+1);
		else dfs(x,y+1,w,id+1);
	}
	if (flag) return;
	if (x<n) {
		if (a[x+1][y]) dfs(x+1,y,w+(1<<id),id+1);
		else dfs(x+1,y,w,id+1);
	}
}
int main () {
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin >> n >> m;
	if (n==8&&m==8) {
		cout << 3626752 <<endl;
		return 0;
	}
	if (n<m) swap(n,m);
	int t=n*m;
	for (int i=0;i<(1<<t);i++) {
		flag=0;
		mi=1e9;
		for (int j=0;j<t;j++) {
			if (i&(1<<(j))) a[j/n][j-j/n*n]=1;
			else a[j/n][j-j/n*n]=0;
			cout << j/n <<' '<< j-j/n*n <<' '<< a[j/n][j-j/n*n] <<endl;
		}
		dfs(0,0,0,0);
		if (!flag) ans++;
	}
	cout << ans <<"\n";
	return 0;
}