比赛 |
202103省实验桐柏一中普及组联赛 |
评测结果 |
TTTTTTTAAT |
题目名称 |
亡羊补牢,未为迟也 |
最终得分 |
20 |
用户昵称 |
fsdh |
运行时间 |
8.109 s |
代码语言 |
C++ |
内存使用 |
3.28 MiB |
提交时间 |
2021-03-22 20:03:57 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n, m, ans = 0x3f, st = 0, g[MAXN][MAXN], v[MAXN][MAXN], d[8][2] = {{1, 2}, {-1, 2}, {2, 1}, {-2, 1}, {1, -2}, {-1, -2}, {2, -1}, {-2, -1}};
bool ok () {
for (int q = 1; q <= n; ++q) {
for (int w = 1; w <= m; ++w) {
if (g[q][w] == 0) return false;
}
}
return true;
}
void dfs (int x, int y, int step) {
g[x][y] ++;
for (int w = 0; w < 8; ++w) {
int xx = x + d[w][0], yy = y + d[w][1];
if (xx < 0 || xx > n || yy < 0 || yy > m) continue;
g[xx][yy] ++;
}
if (ok()) {
if (ans > step) {
ans = step;
st = 1;
}
else if (ans == step) st ++;
}
for (int q = 1; q <= n; ++q) {
for (int w = 1; w <= m; ++w) {
if (v[q][w] == 0) {
v[q][w] = 1;
dfs (q, w, step + 1);
v[q][w] = 0;
}
}
}
g[x][y] --;
for (int w = 0; w < 8; ++w) {
int xx = x + d[w][0], yy = y + d[w][1];
if (xx < 0 || xx > n || yy < 0 || yy > m) continue;
g[xx][yy] --;
}
}
int main () {
memset (v, 0, sizeof (v));
freopen ("secretnum.in", "r", stdin);
freopen ("secretnum.out", "w", stdout);
scanf ("%d%d", &n, &m);
for (int q = 1; q <= n; ++q) {
for (int w = 1; w <= m; ++w) {
dfs (q, w, 1);
}
}
for (int q = 2; q <= ans; ++q) {
st /= q;
}
printf ("%d %d\n", ans, st);
return 0;
}