| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2792 人关注过本帖
标题:不会做这个,求帮忙
只看楼主 加入收藏
a18371121175
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2016-12-21
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:4 
不会做这个,求帮忙
马满覆盖问题(中国象棋)
问题描述:在中国象棋棋盘上,如果在放置若干个马后,使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉,则称这组放置为棋盘上的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖,则称这一满覆盖为极小满覆盖。
要求:
1)求解一个极小满覆盖
2)最好能画出棋盘的图形形式,并在其上动态地演示试探过程;
3)程序能方便地移植到其他规格的棋盘上;
4)需要考虑中国象棋“别腿”的规定;
搜索更多相关主题的帖子: 中国象棋 规格 动态 最好 
2016-12-22 12:04
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:20 
第一眼以为是八皇后问题的变种,后面发现不是,皇后的个数并不确定,而且中国象棋的棋盘 9*10 问题复杂度也上升了不少,mark一下,一会儿研究看看。


[fly]存在即是合理[/fly]
2016-12-22 14:56
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
把马放满棋盘是极小满覆盖

010101
101010
010101

也是极小满覆盖

这两种选一个就可以


[fly]存在即是合理[/fly]
2016-12-23 23:06
a18371121175
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2016-12-21
收藏
得分:0 
#include <stdio.h>
#define max_h 9
#define max_s 10
chesschess()//构造函数的实现
{
int attack[max_h][max_s];
 for(int i= 0;i<max_s;i++)
 {
  for(int j=0;j<max_s;j++)
  {
   cover[i][j]='N';//棋盘初始状态都是没放马
        attack[i][j]=0;//受攻击次数都为0
  }
 }
 max_i=0;//受攻击最多的马坐标?0 ?0?
 max_j=0;
}
void chess::get_attack(){//受攻击次数数组的实现
 for(int i = 0; i < max_h;i++){
    for(int j=0;j<max_s;j++){
   if(i-1>=0&&j-2>=0){attack[i-1][j-2]++;}//
将当前位置的-1.-2方向的位置被吃次数加1
   if(i-1>=0&&j+2<max_s){ attack[i-1][j+2]++;}
//将当前位置的-1.2方向的位置被吃次数加1 ?
   if(i-2>=0&&j-1>=0){attack[i-2][j-1]++;}//
将当前位置的-2.-1方向的位置被吃次数加1
   if(i-2>=0&&j+1<max_s){attack[i-2][j+1]++;}//
将当前位置的-2.1方向的位置被吃次数加1
if(i+1<max_h&&j-2>=0){attack[i+1][j-2]++;}//
将当前位置的1.-2方向的位置被吃次数加1
  if(i+1<max_h&&j+2<max_s){attack[i+1][j+2]++;}//
将当前位置的1.2方向的位置被吃次数加1
  if(i+2<max_h&&j-1>=0){attack[i+2][j-1]++;}//将
当前位置的2.-1方向的位置被吃次数加1
if(i+2<max_h&&j+1<max_s ){ attack[i+2][j+1]++;}//将当前
位置的2.1方向的位置被吃次数加1}
}
}
//坐标?a,b?上放马对攻击次数的影响
void chess::to_attack(int a,int b){
  if(a-1>=0&&attack[a-1][b]!= 0)//其蹩(a-1,b)
位置上的马吃(a+1,b-1)和(a+1,b+1)上的马
   {if(a+1<max_h && b-1 >= 0&&cover[a+1][b-1]=='N')
attack[a+1][b-1]--;
   if(a+1<max_h && b+1 <max_s&&cover[a+1][b+1]=='N')
attack[a+1][b+1]--;}
        if(a+1 <max_h && attack[a+1][b] != 0){
   if(a-1 >= 0 && b-1 >= 0&&cover[a-1][b-1]=='N')
attack[a-1][b-1]--;
   if(a-1 >= 0 && b+1 <max_s&&cover[a-1][b+1]=='N')
   attack[a-1][b+1]--;}
  if(b+1 <max_h &&  attack[a][b+1] != 0){
   if(a+1 <max_h&& b-1 >= 0&&cover[a+1][b-1]=='N')
attack[a+1][b-1]--;
   if(a-1 >= 0 && b-1>= 0&&cover[a-1][b-1]=='N')
attack[a-1][b-1]--;}
  if(b-1>= 0 &&  attack[a][b-1] != 0){
   if(a-1 >= 0 && b+1 <max_s&&cover[a-1][b+1]=='N')
attack[a-1][b+1]--;
   if(a+1 >= 0 && b+1 <max_s&&cover[a+1][b+1]=='N')
attack[a+1][b+1]--;
  }
 }
    void chess::get_horse(){//得到攻击次数最高的马的函
数实现
  max = attack[0][0];//用 Max暂时储存被吃次数最多的
位置上被吃次数?中间变量
     for(int i = 0; i < max_s; i++){
      for(int j = 0; j < max_s; j++){
       if(attack[i][j] > max){
        max = attack[i][j];
        max_i = i;
         max_j = j;
    }
   }
  }
 }
 void chess::put_horse()//放马的实现
 {
  if(attack[max_i][max_j] >= 0 )
  { //用数组Attack[Max_i][Max_j]储存被吃几率最大位置
上的被吃次数  
  cover[max_i][max_j] = '*';//在覆盖数组中标志此位置
为已放马.
  attack[max_i][max_j] =0;//不能忘记将该位置也标记已
放马。  
 if(max_i-1>=0&&max_j-2>=0&&cover[max_i][max_j-1]!='*
'){   
            cover[max_i-1][max_j-2]='Y';
         attack[max_i-1][max_j-2]=0;}   
if(max_i-1>=0&&max_j+2<max_s&&cover[max_i][max_j+1]!='*
') {
   cover[max_i-1][max_j+2]='Y';
         attack[max_i-1][max_j+2] = 0;}
         if(max_i-2>=0&&max_j+1<max_s&&cover[max_i-1][max_j]!
='*') {
   cover[max_i-2][max_j+1]='Y';
         attack[max_i-2][max_j+1] = 0;}
 if(max_i-2>=0&&max_j-1>0&&cover[max_i-1][max_j]!='*')
{
   cover[max_i-1][max_j+2]='Y';
         attack[max_i-1][max_j+2] = 0;}
 if(max_i+1<max_h&&max_j-2>0&&cover[max_i][max_j-1]!=
'*') {
   cover[max_i+1][max_j-2]='Y';
         attack[max_i+1][max_j-2] = 0;
  }
  if(max_i+1<max_h &&
max_j+2<max_s&&cover[max_i][max_j+1]!='*') {
   cover[max_i+1][max_j+2]='Y';
         attack[max_i+1][max_j+2] = 0;
  }
  if(max_i+2<max_h &&
max_j-1>0&&cover[max_i+1][max_j]!='*') {
   cover[max_i+2][max_j-1]='Y';
         attack[max_i+2][max_j-1] = 0;
         }
 if(max_i+2<max_h&&max_j+1<max_s&&cover[max_i+1][max_
j]!='*') {
   cover[max_i+2][max_j+1]='Y';
         attack[max_i+2][max_j+1] = 0;
  }
  to_attack(max_i,max_j);
  }
 }
 void chess::get_cover()//得到最小覆盖函数的实现
 {
  while(1){
   do{
    get_horse();
    if(max!=0&&cover[max_i][max_j]!='N')
     return;
   }while(cover[max_i][max_j]!='N');
    put_horse();
  }
 }
 void chess::print_out()//输出棋盘函数的实现
 { for(int i = 0; i < max_s; i++){
  for(int j = 0; j < max_s; j++){
   cout<<cover[i][j]<<" ";
  }
  cout<<endl;
 }
 }
//主函数的实现
Void main??{
Chess c;//定义一个对象
c.get_attack();//生成攻击表格
 c.get_cover();//完成极小覆盖的求解
 c.print_out();//输出棋盘
}
2016-12-29 13:16
a18371121175
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2016-12-21
收藏
得分:0 
这个代码能帮我看一下吗?
2016-12-29 13:17
快速回复:不会做这个,求帮忙
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022367 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved