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