比赛 |
202103省实验桐柏一中普及组联赛 |
评测结果 |
AAAAAAAAWA |
题目名称 |
亡羊补牢,未为迟也 |
最终得分 |
90 |
用户昵称 |
yrtiop |
运行时间 |
0.033 s |
代码语言 |
C++ |
内存使用 |
10.19 MiB |
提交时间 |
2021-03-22 21:23:49 |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30;
bool vis[maxn][maxn];
bool inq[maxn][maxn];
int lg[1 << 23];
int fx[] = {0 , 1 , 1 , 2 , 2 , -1 , -1 , -2 , -2};
int fy[] = {0 , 2 , -2 , 1 , -1 , -2 , 2 , 1 , -1};
int n,m;
int ans = 0,cur = 0;
bool judge(int x,int y) {
return x >= 1&&x <= n&&y >= 1&&y <= m;
}
void dfs(int x,int y,int cnt,int all) {
if(y > m) {
++ x;
y = 1;
}
if(x > n) {
if(!all) {
if(ans > cnt) {
ans = cnt;
cur = 1;
return ;
}
if(ans == cnt) {
++ cur;
return ;
}
return ;
}
return ;
}
dfs(x , y + 1 , cnt , all);
bool p[10];
int sum = 0;
for(int k = 0;k <= 8;++ k) {
int nx = x + fx[k];
int ny = y + fy[k];
if(judge(nx , ny)) {
p[k] = vis[nx][ny];
if(!vis[nx][ny])++ sum;
vis[nx][ny] = true;
}
}
dfs(x , y + 1 , cnt + 1 , all - sum);
for(int k = 0;k <= 8;++ k) {
int nx = x + fx[k];
int ny = y + fy[k];
if(judge(nx , ny)) {
vis[nx][ny] = p[k];
}
}
return ;
}
int main() {
freopen("secretnum.in","r",stdin);
freopen("secretnum.out","w",stdout);
scanf("%d %d",&n,&m);
ans = n * m;
cur = 1;
memset(vis , 0 , sizeof(vis));
dfs(1 , 1 , 0 , n * m);
printf("%d %d",ans,cur);
fclose(stdin);
fclose(stdout);
return 0;
}