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