在中国象棋中，最少用多少只马才能控制住整个棋盘？（马控棋盘）？ 第1页

最少22。

只用22只马的最优解应该是260种，考虑有棋盘上下对称的结果的话就是130种。

用的是DFS+剪枝。跑了两次DFS，一次求出最优解需要用到的马的个数是22，第二次找出22只马所有可能的解。跑了一个多小时。（其实跑一次应该就可以了，懒得改了直接复制了代码里第一次的DFS= =）

主要的剪枝是考虑落子后，如果继续下去此点之前的某个点无论如何也不能控制，则返回。

代码和解法如下（只传前30种解法吧，太多了。。。

）：

#include <stdio.h>

#include <memory.h>

#include <stdlib.h>

int fi,fj;

typedef struct Point{

int x;

int y;

}Point;

int check_w(int * path,int i,int j){

if((i>=0 && i<10) && (j>=0 && j<9)){

if(path[i*9+j]){

return 1;

}

}

return 0;

}

void in_reg(int ** use,Point * newp,int * newpc,int i,int j){

if((i>=0 && i<10) && (j>=0 && j<9)){

if(use[i][j]){

return;

}

newp[*newpc].x=i;

newp[*newpc].y=j;

(*newpc)++;

use[i][j]=1;

}

}

void to_use(int ** use,Point * newp,int * newpc,int i,int j){

in_reg(use,newp,newpc,i,j);

in_reg(use,newp,newpc,i-2,j-1);

in_reg(use,newp,newpc,i-1,j-2);

in_reg(use,newp,newpc,i+1,j-2);

in_reg(use,newp,newpc,i+2,j-1);

in_reg(use,newp,newpc,i-2,j+1);

in_reg(use,newp,newpc,i-1,j+2);

in_reg(use,newp,newpc,i+1,j+2);

in_reg(use,newp,newpc,i+2,j+1);

}

void dfs2path(int ** use,int usc,int * path,int minuse,int nowuse,int nowi,int nowj){

int i,j,k,l,m,newpc;

Point newP[9];

if(nowuse> minuse){

return;

}

if(usc==90){

if(nowuse== minuse){

k=0;

for(i=0;i<10;i++){

for(j=0;j<9;j++){

if(path[i*9+j]){

printf("M");

k++;

}else{

printf(".");

}

}

printf(" ");

}

printf(" ");

}

return;

}

for(i=nowi;i<10;i++){

for(j=0;j<9;j++){

if(i==nowi && j<nowj){

continue;

}

if(check_w(path,i-1,j)|| check_w(path,i+1,j)||check_w(path,i,j-1) ||check_w(path,i,j+1)){

continue;

}

if(i>nowi+4){

return;

}

for(l=0;l<i-2;l++){

for(m=0;m<9;m++){

if(!use[l][m]){

return;

}

}

}

l=i-2;

if(l>=0){

for(m=0;m<j-1;m++){

if(!use[l][m]){

return;

}

}

}

newpc=0;

to_use(use,newP,&newpc,i,j);

path[i*9+j]=1;

if(j>=8){

dfs2path(use,usc+newpc,path,minuse,nowuse+1,i+1,0);

}else{

dfs2path(use,usc+newpc,path,minuse,nowuse+1,i,j+1);

}

path[i*9+j]=0;

for(k=0;k<newpc;k++){

use[newP[k].x][newP[k].y]=0;

}

}

}

}

void dfs(int ** use,int usc,int * path,int * minuse,int nowuse,int nowi,int nowj){

int i,j,k,l,m,newpc;

Point newP[9];

if(nowuse>= *minuse){

return;

}

if(usc==90){

if(nowuse< *minuse){

*minuse=nowuse;

}

return;

}

for(i=nowi;i<10;i++){

for(j=0;j<9;j++){

if(i==nowi && j<nowj){

continue;

}

if(i>nowi+4){

return;

}

if(check_w(path,i-1,j)|| check_w(path,i+1,j)||check_w(path,i,j-1) ||check_w(path,i,j+1)){

continue;

}

for(l=0;l<i-2;l++){

for(m=0;m<9;m++){

if(!use[l][m]){

return;

}

}

}

l=i-2;

if(l>=0){

for(m=0;m<j-1;m++){

if(!use[l][m]){

return;

}

}

}

newpc=0;

to_use(use,newP,&newpc,i,j);

path[i*9+j]=1;

if(j>=8){

dfs(use,usc+newpc,path,minuse,nowuse+1,i+1,0);

}else{

dfs(use,usc+newpc,path,minuse,nowuse+1,i,j+1);

}

path[i*9+j]=0;

for(k=0;k<newpc;k++){

use[newP[k].x][newP[k].y]=0;

}

}

}

}

int main(){

int ** use,i,j,minuse,psc,usc;

int * ps;

minuse=90;

use=(int **)malloc(sizeof(int *)*10);

ps=(int *) malloc(sizeof(int)*90);

memset(ps,0,sizeof(int)*90);

for(i=0;i<10;i++){

use[i]=(int * )malloc(sizeof(int)*9);

memset(use[i],0,sizeof(int)*9);

}

dfs(use,0,ps,&minuse,0,0,0);

printf("minuse:%d ",minuse);

memset(ps,0,sizeof(int)*90);

for(i=0;i<10;i++){

memset(use[i],0,sizeof(int)*9);

}

dfs2path(use,0,ps,minuse,0,0,0);

return 0;

}