比赛 202103省实验桐柏一中普及组联赛 评测结果 WWWWWWWWWW
题目名称 亡羊补牢,未为迟也 最终得分 0
用户昵称 增强型图元文件 运行时间 0.003 s
代码语言 C++ 内存使用 3.76 MiB
提交时间 2021-03-22 21:20:10
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int mp[21][21];
bool pl[21][21]={0};
int n,m;
int r[9][2]={{0,0},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
bool l[1145][21][21]={0};
int pcnt=0;
void addcnt(){
    pcnt++;
    for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             l[pcnt][i][j]=pl[i][j];
         }
     }
}
void add(int x,int y){
     for(int i=0;i<9;i++){
         int tx=x+r[i][0],ty=y+r[i][1];
         if((tx>0&&tx<=n)&&(ty>0&&ty<=m)){
             mp[tx][ty]++;
         }
     }
}
void remove(int x,int y){
     for(int i=0;i<9;i++){
         int tx=x+r[i][0],ty=y+r[i][1];
         if((tx>0&&tx<=n)&&(ty>0&&ty<=m)){
             mp[tx][ty]--;
         }
     }
}
bool check(int x,int y){
    for(int k=0;k<=pcnt;k++){
        bool f=true;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(l[k][i][j]!=pl[i][j]){
                    f=false;
                }
            }
        }
        if(f){
            return false;
        }
    }
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             if(!mp[i][j])return false;
         }
     }
     return true;
}
int dfs(int cur,int maxq){
    if(cur==maxq){
       int tmtot=0;
       for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
               if(!pl[i][j]){
                  add(i,j);
                  pl[i][j]=1;
                  if(check(i,j)){
                      tmtot++;
                      addcnt();
                  }
                  pl[i][j]=0;
                  remove(i,j);
               }
           }
       }
       return tmtot;
    }
    int tmtot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!pl[i][j]){
                add(i,j);
                pl[i][j]=1;
                tmtot+=dfs(cur+1,maxq);
                pl[i][j]=0;
                remove(i,j);
            }
        }
    }
    return tmtot;
}
int main(int argc, char** argv) {
    freopen("secretnum.in","w",stdout);
    freopen("secretnum.out","w",stdout);
            memset(mp,0,sizeof(mp));
            memset(pl,0,sizeof(pl));
            memset(l,0,sizeof(l));
            pcnt=0;
            cin>>n>>m;
            if(n==1){
                cout<<m<<endl;
                return 0;
            }
            int tp=1;
            int tres=0;
            while(!(tres=dfs(1,tp))){
                tp++;
            }
    cout<<tp<<" "<<tres<<endl;
	return 0;
}