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