| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 648 人关注过本帖
标题:[讨论]马的极小覆盖问题
只看楼主 加入收藏
bluemoon
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2006-6-26
收藏
 问题点数:0 回复次数:1 
[讨论]马的极小覆盖问题
在8*8的国际象棋棋盘上,如果放置若干个马后,使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉,则称这组放置为棋盘的一个满覆盖。若取掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖,则称这一满覆盖为极小满覆盖。沙棘程序完成如下要求:

1、求解一个极小满覆盖。

2、最好能画出棋盘的图形形式,并在其上动态地显示试探过程。

3、程序能方便地移植到其他规格的棋盘上

#include<iostream>
#include<vector>
using namespace std;
const int n=8;
int a[n][n];
int b[n][n];
int num1=64;
//1表示是放马
//0表示没有放马且没有马可以攻击到的位置
//2表示马的可攻击位置
int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
void fg(int ix,int iy){
if(ix>=0&&ix<n&&iy>=0&&iy<n)
{
for(int iz=1;iz>=0;iz--)
//int iz=1;
{
if(a[ix][iy]!=2||iz!=0)///
{
int q=a[ix][iy];
vector<int> save;
a[ix][iy]=iz;
if(iz==1)
{
for(int i=0;i<8;i++)
{
if(ix+dir[i][0]>=0&&ix+dir[i][0]<n&&iy+dir[i][1]>=0&&iy+dir[i][1]<n)
{
if(a[ix+dir[i][0]][iy+dir[i][1]]==0)
{
a[ix+dir[i][0]][iy+dir[i][1]]=2;
int bb=(iy+dir[i][1])+n*(ix+dir[i][0]);
save.insert(save.end(),bb);
}//if
}//if
}//for
}//if
fg((iy+1)/n+ix,(iy+1)%n);
int item=1;
int num=0;
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
{
if(a[j][k]==0)
{
item=0;break;//return;
}//if
if(a[j][k]==1)
{
num++;
}
}//for
if(item&&num<num1)
{
//cout << num <<endl;
num1=num;
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
cout << a[j][k] << " ";
b[j][k]=a[j][k];
}
cout <<endl;
}//for
system("pause");
}//if
a[ix][iy]=q;
//cout << q <<endl;
vector<int>::const_iterator it=save.begin();
while(it!=save.end())
{
int i0,i1;
i0=*it%n;
i1=*it/n;
a[i1][i0]=0;
it++;
}//while */
}
}//for
}
}
int main()
{
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
a[j][k]=0;
fg(0,0);
cout << num1 <<endl;
for(j=0;j<n;j++)
{
for(int k=0;k<n;k++)
cout << b[j][k] << " ";
cout <<endl;
}
system("pause");
return 0;
}


可是做的很有问题,谁帮忙看看阿,别管效率啦!至少要过去再说
搜索更多相关主题的帖子: 图形 国际象棋 include 规格 
2006-06-26 00:09
bluemoon
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2006-6-26
收藏
得分:0 
不行了,谁帮帮忙,给个源码吧
2006-06-26 07:21
快速回复:[讨论]马的极小覆盖问题
数据加载中...
 
   



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

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