文档章节

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

侯禹
 侯禹
发布于 2013/07/09 23:10
字数 326
阅读 105
收藏 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);
 }
}
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
ACM-ICPC参赛者人手一册讲解算法的书,你准备了没?

《挑战程序设计竞赛》迷你书下载 http://vdisk.weibo.com/s/Kr8nZ 世界顶级程序设计高手的经验总结 【ACM-ICPC全球总冠军】巫泽俊主译 日本ACM-ICPC参赛者人手一册 先来介绍一下我们这本应该...

生气的散人
2013/07/18
347
3
小朋友学经典算法(14):回溯法和八皇后问题

一、回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不...

海天一树X
10/09
0
0
神级竞赛ACM,究竟能为你的职场加分多少?

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

100offer
07/04
0
0
回溯算法思想与八皇后问题解的个数

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

silenceyawen
03/04
24
0
退役了,永远的ACMer,永远的ProLights

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

prolightsfxjh
03/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux脚本中父shell与子shell 执行的几种方式

本文主要介绍以下几个命令的区别: shell subshell source $ (commond) `commond` Linux执行Scripts有两种方式,主要区别在于是否建立subshell 1. source filename or . filename 不创建sub...

问题终结者
15分钟前
1
0
安装jdk和Tomcat

12月12日任务 16.1 Tomcat介绍 16.2 安装jdk 16.3 安装Tomcat Tomcat介绍 Tomcat是apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由apache、Sun和其他一些...

robertt15
16分钟前
3
0
Beetl 免费视频

来自 https://my.oschina.net/gking?q=Beetl ,Beetl终于有人录制视频了 项目git地址:https://gitee.com/gavink/beetl-blog 视频地址:下载下来会更清晰,视频比较长,可使用倍速看 百度网盘...

闲大赋
28分钟前
0
0
isEmpty和null的区别

isEmpty和null的区别: 1.一个是对象为空(IsNull),一个是值为空(IsEmpty) 2.IsNull指任务类型变量是否为空包括对象类型的变量。 IsNull函数: 功能:返回Boolean的值,指明表达是否不包...

DemonsI
55分钟前
3
0
Centos7 安装mysql与php

https://blog.csdn.net/qq_36431213/article/details/79576025 官网下载安装mysql-server 依次使用下面三个命令安装 wget http://dev.mysql.com/get/mysql-community-release-el7-5.noarch.r......

Yao--靠自己
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部