比赛 202103省实验桐柏一中普及组联赛 评测结果 WWWWWWWWAW
题目名称 亡羊补牢,未为迟也 最终得分 10
用户昵称 _Hzm_ 运行时间 0.021 s
代码语言 C++ 内存使用 0.40 MiB
提交时间 2021-03-22 17:52:00
显示代码纯文本
#include <cstdio>
#include <cstring>

#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

int n, m, s, t, vis[21][21];

int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

inline bool pd()
{
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(vis[i][j] == 0)
				return false;
	return true;
}

void dfs(int x, int y, int sum)
{
	//printf("%d %d %d\n", x, y, sum);
	int pds = pd();
	if(pds)
	{
		s = min(s, sum);
		++t;
		return ;
	}
	if(y > m && !pds)
		return ;
	if(x == n)
		dfs(1, y + 1, sum);
	else
		dfs(x + 1, y, sum);
	++vis[x][y];
	for(int i = 0; i < 8; i++)
		if(x + dx[i] > 0 && x + dx[i] <= n && y + dy[i] > 0 && y + dy[i] <= m)
			++vis[x + dx[i]][y + dx[i]];
	if(x == n)
		dfs(1, y + 1, sum + 1);
	else
		dfs(x + 1, y, sum + 1);
	--vis[x][y];
	for(int i = 0; i < 8; i++)
		if(x + dx[i] > 0 && x + dx[i] <= n && y + dy[i] > 0 && y + dy[i] <= m)
			--vis[x + dx[i]][y + dx[i]];
	return ;
}

int main()
{
	freopen("secretnum.in", "r", stdin);
	freopen("secretnum.out", "w", stdout);
	scanf("%d %d", &n, &m);
	s = n * m;
	if(n > m)
	{
		int tmp = n;
		n = m;
		m = tmp;
	}
	dfs(1, 1, 0);
	printf("%d %d", s, t);
	fclose(stdin);
	fclose(stdout);
	return 0;
}