比赛 202103省实验桐柏一中普及组联赛 评测结果 MMMMMMMMMM
题目名称 亡羊补牢,未为迟也 最终得分 0
用户昵称 tb_guobinbin 运行时间 0.000 s
代码语言 C++ 内存使用 256.00 MiB
提交时间 2021-03-22 18:06:47
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s=21,t=0;
int ax[8]={2,2,1,1,-1,-1,-2,-2};
int ay[8]={1,-1,2,-2,2,-2,1,-1};
bool sf[1048577][21][21]={};
int f=0,b=1;
int x[10000000],y[10000000];
int gs[10000000]={};
bool bl;
int main(){
	freopen("secretnum.in","r",stdin);
	freopen("secretnum.out","w",stdout);
	cin>>n>>m;
	if(n<m){
		t=m;
		m=n;
		n=t;
		t=0;
	}
	if(n==1){
		cout<<m<<" 1";
		fclose(stdin);
		fclose(stdout);
		return 0;
	}
	if(m==1){
		cout<<n<<" 1";
		fclose(stdin);
		fclose(stdout);
		return 0;
	}
	x[1]=1,y[1]=1;
	while(f<b){
		f++;
		if(y[f]<m&&x[f]<=n){
			b+=2;
			x[b]=x[b-1]=x[f];
			y[b]=y[b-1]=y[f]+1;
			gs[b]=gs[f]+1;
			gs[b-1]=gs[f];
		}else{
			if(x[f]<=n){
				b+=2;
				x[b]=x[b-1]=x[f]+1;
				y[b]=y[b-1]=1;
				gs[b]=gs[f]+1;
				gs[b-1]=gs[f];
			}else{
				bl=true;
				for(register int i=1;i<=n;i++){
					for(register int j=1;j<=m;j++){
						if(sf[f][i][j]==false){
							bl=false;
							break;
						}
					}
					if(bl==false){
						break;
					}
				}
				if(bl==true){ 
					if(s==gs[f]){
						t++;
					}else{
						if(gs[f]<s){
							s=gs[f];
							t=1;
						}
					}
				}
				continue;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sf[b][i][j]=sf[b-1][i][j]=sf[f][i][j];
			}
		}
		for(int j=0;j<8;j++){
			if(x[f]+ax[j]>0&&x[f]+ax[j]<=n&&y[f]+ay[j]>0&&y[f]+ay[j]<=n)
			sf[b][x[f]+ax[j]][y[f]+ay[j]]=true;
		}
		sf[b][x[f]][y[f]]=true;
	}
	cout<<s<<" "<<t;
	fclose(stdin);
	fclose(stdout);
	return 0;
}