比赛 |
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;
}