记录编号	559844	评测结果	AWAAWWAWWW
题目名称	亡羊补牢，未为迟也	最终得分	40
用户昵称	Sicly	是否通过	未通过
代码语言	C++	运行时间	0.103 s
提交时间	2021-03-24 20:40:30	内存使用	1.31 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=10,M=10;
const int dx[9] = {0,-2,-1,1,2,2,1,-1,-2};
const int dy[9] = {0,-1,-2,-2,-1,1,2,2,1};
int n,m,cnt[N*M+1]={0},val[N][M],minnum,found;
bitset<N*M> b;

int check(int aai)//检验数字i的二进制对应的方案是否可行
{
	memset(val,0,sizeof(val));//防御值初始化
	int num=0;//记录有多少个区域被防御
	for(int j=0;j<b.size();j++)
	{//枚举二进制中的每一个1，即有暗哨的位
		if(b[j]==1)//如果某一位是1
		{
			int p=j+1;//第几位为1,设最右边为第1位
			int x,y;//位置p对应的行列号 
			x=p/m+1;y=p%m;//计算二进制串中的位置p对应的行列位置(x,y)
			val[x][y]=1;//标记暗哨位置为 1
			for(int k=1;k<=8;k++)//标记暗哨的8个防御区域
			{
			    if((x+dx[k]>0)&&(y+dy[k]>0))
			    {
                    val[x+dx[k]][y+dy[k]]=1;
                }
            }
		}
	}
	for(int i=1;i<=n;i++)//遍历val[][]累加num
	{
	    for(int j=1;j<=m;j++)
	    {
	        num+=val[i][j];
        }
    }
    cout<<endl;
	if(num==n*m)//全营太平
	{
        cnt[b.count()]++;
        if(b.count()<minnum)minnum=b.count();
    }
    //{累加和更新答案}
	return 0;
}

int main()
{
	freopen("secretnum.in","r",stdin);
	freopen("secretnum.out","w",stdout);
	cin>>n>>m;
	found=0;minnum=n*m+1;
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=(1ull<<n*m)-1;i++)
	{//枚举 00...1  -->  11...1
		b=i;
		if(b.count()>minnum)continue;//剪枝
		check(i);//检验数字i的二进制对应的方案是否可行
	}
	cout<<minnum<<' '<<cnt[minnum]<<endl;
	return 0;
}