文档章节

菜鸟一枚,心血来潮用PHP整理一下ACM/ICPC的算法.....(八皇后)

侯禹
 侯禹
发布于 2013/07/09 23:10
字数 326
阅读 103
收藏 0

其实就是一种,利用递归实现的DFS,每当一个行上面的皇后确定了位置之后,再走下一个皇后的,实现一次便打印一次~

<?php
$m=new a();
$m->man();
?>
<?php
class a{
protected $n=8;//棋盘的格子数(横、纵)
public $x=array();//定义棋盘二维数组
public $s=0;//到第几种方案了
 public function is_ok($t)//判断是否符合条件(即不同行,不同斜线)
 {
  for($i=0;$i<$t;$i++)
  if($this->x[$t]==$this->x[$i]||ABS($this->x[$t]-$this->x[$i])==ABS($t-$i))return false;
  return true;
 }
 
 function dayin()//将一种方案打印出来
 {
  echo "this is ".$this->s.":<br>";
  $this->s++;
  for($i=0;$i<$this->n;$i++){
   for($j=0;$j<$this->n;$j++){
    if($this->x[$i]==$j)echo "@";//如果本i行的棋子确实被放到了j列,则打印出皇后
    else echo "#";
   }
   echo "<br>";
  }
 }
 
 function dfs($t)//深搜,主要的代码部分
 {
  if($t==8)$this->dayin();//如果递归到最后一层的时候(八个棋子都安置完),则打印
  else
  {
   for($i=0;$i<$this->n;$i++)
   {
    $this->x[$t]=$i;//试探性的将第t行的棋子放在t列
    if($this->is_ok($t))//判断是否符合条件
    $this->dfs($t+1);//如果符合条件则放置下一行的棋子
   }
  }
 }
 function man()
 {
  $this->dfs(0);
 }
}
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
神级竞赛ACM,究竟能为你的职场加分多少?

注:ACM 竞赛全称为 ACM 国际大学生程序设计竞赛,英文全称:ACM International Collegiate Programming Contest,简称 ACM-ICPC 或 ICPC )。因为大家习惯简称为 ACM,文章中出现的 ACM 若无...

100offer
07/04
0
0
退役了,永远的ACMer,永远的ProLights

三年从一个什么都不懂的小司机成为了金牌在手的大司机,现在退役又变成了退役司机了。加入uestc-acm集训队大家庭,这三年来学了很多,感谢uestc-acm,感谢我的历届队友cx大爷、钟司机、nardo...

prolightsfxjh
03/25
0
0
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

silenceyawen
03/04
24
0
【算法】数据结构与算法之美,解剖艺术

Preface   因为最近一直在搞硬件的东西,所以暂时没管自己专业的东西,昨晚一童鞋问到一个网络里面的算法时,突然发现自己的强项,已然不是强项了,于是总结了一下   硬件的东西,其实是...

wbf961127
2017/11/08
0
0
考研复试系列——第四节 深度优先搜索

考研复试系列——第四节 深度优先搜索 前言 dfs:if(判断条件) //在这里进行递归的退出return;for(遍历内容) //进行遍历,例如图中访问每一个满足某一条件的节点{if(判断是否访问过以及其他题...

cassiepython
2017/03/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之高级类型的字符串字面量类型

转发TypeScript基础入门之高级类型的字符串字面量类型 高级类型 字符串字面量类型 字符串字面量类型允许你指定字符串必须的固定值。 在实际应用中,字符串字面量类型可以与联合类型,类型保护...

durban
16分钟前
2
0
iOS权限授权添加

<!-- 相册 --> <key>NSPhotoLibraryUsageDescription</key> <string>App需要您的同意,才能访问相册</string> <!-- 相册写入 --> <key>NSPhotoLibraryAddUsageDescription</key> <string>App......

RainOrz
20分钟前
1
0
支配树(Dominator Tree)

MAT中的支配树 在使用MAT分析项目的内存泄漏问题时,其中有一个支配树(Dominator)视图。如果我们把Java对象之间的引用关系看做一张有向图(可以存在环)的话,对象的支配树体现了对象之间的...

akane_oimo
22分钟前
1
0
xshell官网下载及安装(免费版本)

百度搜索xshell,点击xshell官网下载链接,如图 然后点击下图的按钮 点击Latest Products,可以下载最新版本,选择要下载的版本,点击下载 选择上面红框里面的,并填写内容,submit之后会有邮...

曾大大胖
27分钟前
2
0
Android 调用系统分享文字、图片、文件,可直达微信、朋友圈、QQ、QQ空间、微博

兼容SDK 18以上的系统,直接调用系统分享功能,分享文本、图片、文件到第三方APP,如:微信、QQ、微博等 因为偷懒,可直达微信、朋友圈、QQ、QQ空间、微博的分享仅写了图片分享的,其他的文本...

她叫我小渝
29分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部