比赛 |
202103省实验桐柏一中普及组联赛 |
评测结果 |
WWWWWWWWAW |
题目名称 |
亡羊补牢,未为迟也 |
最终得分 |
10 |
用户昵称 |
_Hzm_ |
运行时间 |
0.021 s |
代码语言 |
C++ |
内存使用 |
0.40 MiB |
提交时间 |
2021-03-22 17:52:00 |
显示代码纯文本
#include <cstdio>
#include <cstring>
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n, m, s, t, vis[21][21];
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
inline bool pd()
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(vis[i][j] == 0)
return false;
return true;
}
void dfs(int x, int y, int sum)
{
//printf("%d %d %d\n", x, y, sum);
int pds = pd();
if(pds)
{
s = min(s, sum);
++t;
return ;
}
if(y > m && !pds)
return ;
if(x == n)
dfs(1, y + 1, sum);
else
dfs(x + 1, y, sum);
++vis[x][y];
for(int i = 0; i < 8; i++)
if(x + dx[i] > 0 && x + dx[i] <= n && y + dy[i] > 0 && y + dy[i] <= m)
++vis[x + dx[i]][y + dx[i]];
if(x == n)
dfs(1, y + 1, sum + 1);
else
dfs(x + 1, y, sum + 1);
--vis[x][y];
for(int i = 0; i < 8; i++)
if(x + dx[i] > 0 && x + dx[i] <= n && y + dy[i] > 0 && y + dy[i] <= m)
--vis[x + dx[i]][y + dx[i]];
return ;
}
int main()
{
freopen("secretnum.in", "r", stdin);
freopen("secretnum.out", "w", stdout);
scanf("%d %d", &n, &m);
s = n * m;
if(n > m)
{
int tmp = n;
n = m;
m = tmp;
}
dfs(1, 1, 0);
printf("%d %d", s, t);
fclose(stdin);
fclose(stdout);
return 0;
}