菜鸟一枚,心血来潮用PHP整理一下ACM/ICPC的算法.....(八皇后)
博客专区 > 侯禹 的博客 > 博客详情
菜鸟一枚,心血来潮用PHP整理一下ACM/ICPC的算法.....(八皇后)
侯禹 发表于5年前
菜鸟一枚,心血来潮用PHP整理一下ACM/ICPC的算法.....(八皇后)
  • 发表于 5年前
  • 阅读 88
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

其实就是一种,利用递归实现的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);
 }
}
?>


标签: PHP ICPC 八皇后
共有 人打赏支持
粉丝 93
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: