比赛 |
202103省实验桐柏一中普及组联赛 |
评测结果 |
WWWWWWAWAW |
题目名称 |
亡羊补牢,未为迟也 |
最终得分 |
20 |
用户昵称 |
op_组撒头屯 |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2021-03-22 21:20:27 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int fx[]={0,-2,-1,1,2,2,1,-1,-2},fy[]={0,1,2,2,1,-1,-2,-2,-1};
int n,m,ans=0x7ffffff,num=0;
bool ok[25][25]={0};
bool wxc(){
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (ok[i][j]==0){
bool p=0;
for (int k=1;k<=8;k++){
if (ok[i+fx[k]][j+fy[k]]==1){
p=1;
break;
}
}
if (p==0){
return 1;
}
}
else{
for (int k=1;k<=8;k++){
if (ok[i+fx[k]][j+fy[k]]==1){
return 1;
}
}
}
}
}
return 0;
}
int dfs(int x,int y,int s){
//cout<<x<<" "<<y<<" "<<s<<endl;
if (y==m+1){
y=1;
x++;
}
if (x==n+1){
if (wxc()==0){
if (s==ans)num++;
if (s<ans){
ans=s;
num=1;
}
}
return 0;
}
dfs(x,y+1,s);
ok[x][y]=1;
dfs(x,y+1,s+1);
ok[x][y]=0;
return 0;
}
int main(){
freopen ("secretnum.in","r",stdin);
freopen ("secretnum.out","w",stdout);
cin>>n>>m;
dfs(1,1,0);
cout<<ans<<" "<<num<<endl;
return 0;
}