比赛 202103省实验桐柏一中普及组联赛 评测结果 WWWWWWAWAW
题目名称 亡羊补牢,未为迟也 最终得分 20
用户昵称 op_组撒头屯 运行时间 0.004 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2021-03-22 21:20:27
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int fx[]={0,-2,-1,1,2,2,1,-1,-2},fy[]={0,1,2,2,1,-1,-2,-2,-1};
int n,m,ans=0x7ffffff,num=0;
bool ok[25][25]={0};
bool wxc(){
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (ok[i][j]==0){
                bool p=0;
                for (int k=1;k<=8;k++){
                    if (ok[i+fx[k]][j+fy[k]]==1){
                        p=1;
                        break;
                    }
                }
                if (p==0){
                    return 1;
                }
            }
            else{
                for (int k=1;k<=8;k++){
                    if (ok[i+fx[k]][j+fy[k]]==1){
                        return 1;
                    }
                }
            }
        } 
    }
    return 0;
}
int dfs(int x,int y,int s){
    //cout<<x<<" "<<y<<" "<<s<<endl;
    if (y==m+1){
        y=1;
        x++;
    }
    if (x==n+1){
        if (wxc()==0){
            if (s==ans)num++;
            if (s<ans){
                ans=s;
                num=1;
            }
        }
        return 0;
    } 
    
    dfs(x,y+1,s);
    ok[x][y]=1;
    dfs(x,y+1,s+1);
    ok[x][y]=0;
    return 0;
} 
int main(){
    freopen ("secretnum.in","r",stdin);
    freopen ("secretnum.out","w",stdout);
    cin>>n>>m;
    dfs(1,1,0);
    cout<<ans<<" "<<num<<endl;
    return 0;
}