比赛 202103省实验桐柏一中普及组联赛 评测结果 AAAAAAAAAA
题目名称 亡羊补牢,未为迟也 最终得分 100
用户昵称 翼德天尊 运行时间 0.026 s
代码语言 C++ 内存使用 0.66 MiB
提交时间 2021-03-22 16:59:02
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define N 25
#define INF 2147483647
typedef long long ll;
int n,m,minn=INF,ans,k;
int dx[9]={0,-2,-2,-1,-1,1,1,2,2};
int dy[9]={0,1,-1,2,-2,2,-2,1,-1};
int ma[N][N];
int read(){
	int w=0,f=1;
	char c=getchar();
	while (c>'9'||c<'0'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		w=(w<<3)+(w<<1)+(c^48);
		c=getchar();
	}
	return w*f;
}
void dfs(int x,int y,int g){
	if (x==n+1&&y==1){
		if (k!=n*m) return;
		if (g<minn) minn=g,ans=1;
		else if (g==minn) ans++;
		return;
	}
	for (int i=0;i<9;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if (xx>=1&&yy>=1&&xx<=n&&yy<=m){
			k+=!ma[xx][yy]++;
		}
	}
	if (y!=m) dfs(x,y+1,g+1);
	else dfs(x+1,1,g+1);
	for (int i=0;i<9;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if (xx>=1&&yy>=1&&xx<=n&&yy<=m){
			k-=!--ma[xx][yy];
		}
	}
	if (y!=m) dfs(x,y+1,g);
	else dfs(x+1,1,g);
}
int main(){
	freopen("secretnum.in","r",stdin);
	freopen("secretnum.out","w",stdout);
	n=read(),m=read();
	dfs(1,1,0);
	printf("%d %d\n",minn,ans);
	return 0;
}