2019 蓝桥杯省赛 A 组模拟赛（一）C. 结果填空：马的管辖 （暴力搜索）

题目：

在中国象棋中，马是走日字的。一个马的管辖范围指的是当前位置以及一步之内能走到的位置，下图的绿色旗子表示马能走到的位置。

如果一匹马的某个方向被蹩马脚，它就不能往这个方向跳了，如下图所示，海星的位置存在旗子，马就不能往上跳到那两个位置了：

那么问题来了，在一个 n\times mn×m 的棋盘内，如何用最少的马管辖住所有 n\times mn×m 个格子。比如 n=m=3n=m=3 时，最少要用 55 只马才能管辖所有棋盘，一种可能的方案如下： 

当 n=m=5时，请你求出用最少马管辖的 方案个数。

分析：

暴力搜索，枚举所有可能的状态（用二进制表示），因为5*5的方格，所以所有可能的状态为0——(1<<25)-1 共25种

注意题目所求的是最少马管辖的方案总数。

代码还是挺容易出错的，要小心

代码：
 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
using namespace std;

int fx[4]={0,0,-1,1};
int fy[4]={-1,1,0,0};
int dx[8]={-1,1,-1,1,-2,-2,2,2};
int dy[8]={-2,-2,2,2,-1,1,-1,1};
int vis[10][10];
int G[10][10];

int main(){
    int n=5,m=5;
    int r=n*m;
    int res=0;//马的数量
    int cnt=0;//覆盖的格子数目
    int mmin=30;//全覆盖需要最少的马
    int ans=0;//用最少的马覆盖的方案数
    for(int s=0;s<(1<<r);s++){
        cnt=0;
        res=0;
        memset(vis,0,sizeof(vis));
        memset(G,0,sizeof(G));
        for(int i=0;i<r;i++){//对于每种状态，将构成状态的图还原出来
            if(s&(1<<i)){
                G[i/n][i%m]=1;
                vis[i/m][i%m]=1;
                res++;
                cnt++;
            }
        }
        if(res>mmin) continue;
        for(int j=0;j<n;j++){//将所有能覆盖到的位置覆盖
            for(int k=0;k<m;k++){
                if(G[j][k]==1){
                    for(int kk=0;kk<4;kk++){
                        int xx=j+fx[kk];
                        int yy=k+fy[kk];
                        if(G[xx][yy]!=1 && xx>=0 && xx<n && yy>=0 && yy<m){
                            for(int mm=2*kk;mm<2*kk+2;mm++){//不蹩脚的话，能覆盖到的位置
                                int mx=j+dx[mm];
                                int my=k+dy[mm];
                                if(!vis[mx][my]&&mx>=0&&mx<n&&my>=0&&my<m){
                                    vis[mx][my]=1;
                                    cnt++;
                                }
                            }
                        }
                    }
                }
            }
        }
        if(cnt!=25) continue;
        if(cnt==25 && res<mmin){
            mmin=res;
            ans=1;
        }
        else if(cnt==25 && res==mmin){
            ans++;
        }
    }
    printf("min: %d\n",mmin);
    printf("plan: %d\n",ans);
    return 0;
}