|
题目：
在中国象棋中，马是走日字的。一个马的管辖范围指的是当前位置以及一步之内能走到的位置，下图的绿色旗子表示马能走到的位置。
如果一匹马的某个方向被蹩马脚，它就不能往这个方向跳了，如下图所示，海星的位置存在旗子，马就不能往上跳到那两个位置了：
那么问题来了，在一个 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;
}
| 
转播
