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

#define int long long

using namespace std;

int ddx[15]={0,1,1,2,2,-1,-1,-2,-2};
int ddy[15]={0,2,-2,1,-1,2,-2,1,-1};

int a[15][15];
int n,m;

int pd(){
	int num=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==1)num++;
			
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1){
				for(int p=1;p<=8;p++){
					int xx=i+ddx[p],yy=j+ddy[p];
					if(xx>n||xx<=0||yy>m||yy<=0)continue;
					a[xx][yy]=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==0)return -1;
		}
	}
	return num;
}

int calcx(int k){
	return (k-1)%n+1;
}

int calcy(int k){
	int x=calcx(k);
	k-=x;
	return k/m+1;
}

int ans=20,cnt=0;

void print(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cout<<a[i][j]<<' ';
		puts("");	
	}
}

void dfs(int k){
	int x=calcx(k),y=calcy(k);
	//cout<<x<<" "<<y<<" "<<k<<" "<<ans<<" "<<cnt<<endl;
	//print();
	//puts("\n");
	if(k==n*m+1){
		int num=pd();
		if(num==-1)return ;
		if(num<ans)ans=num,cnt=0;
		if(num==ans)cnt++;
		return ;
	}
	a[x][y]=1;
	dfs(k+1);
	a[x][y]=0;
	dfs(k+1);
}

signed main(void){
	
	freopen("secretnum.in","r",stdin);
	freopen("secretnum.out","w",stdout);

	cin>>n>>m;
	if(n==1||m==1){
		cout<<max(n,m)<<" "<<1<<endl;
		return 0;
	}
	dfs(1);
	cout<<ans<<" "<<cnt<<endl;

	return 0;
}