文档章节

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

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


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 49
码字总数 34362
作品 0
海淀
程序员
退役了,永远的ACMer,永远的ProLights

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

prolightsfxjh ⋅ 03/25 ⋅ 0

回溯算法思想与八皇后问题解的个数

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

silenceyawen ⋅ 03/04 ⋅ 0

【算法】数据结构与算法之美,解剖艺术

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

wbf961127 ⋅ 2017/11/08 ⋅ 0

有java编写埃氏算法求n以内素数

菜鸟一枚,今天听说有个埃氏算法可以求素数,于是自己用Java编写 了个简单的埃氏算法 来求素数,写完,调试一下程序,并没有出现预期的结果。要是有大神能分享一个java编写的埃氏算法求素数的...

Golden牙 ⋅ 2015/05/04 ⋅ 0

考研复试系列——第四节 深度优先搜索

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

cassiepython ⋅ 2017/03/01 ⋅ 0

算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy ⋅ 2017/10/23 ⋅ 0

回溯法/深度优先遍历的简单优化技巧

深度优先遍历配合回溯,是解决很多问题的好方法,比如八皇后问题。 皇后的排布规则:n个皇后放在n*n的矩阵里,要求一列只有一个,一行只有一个,任一斜线上只有一个(/和)。 通常,我们会把...

刘地 ⋅ 2012/11/17 ⋅ 0

有哪些好的刷题网站?2017年最受欢迎的编程挑战网站

编程几乎已经成为了人类所知每个行业的必要组成部分,如今有越来越多的人开始了他们的编程之旅。 如果你正在在学习编程,那么我可以告诉你一个提高技能的好方法,那就是敢于去解决编码过程中...

ToEnd ⋅ 2017/12/17 ⋅ 0

迭代回溯 ---8皇后

八皇后问题 就是在8*8格子上放8个皇后 皇后是可以横行竖行斜行行走 他们之间不能存在可以被吃的关系 算法 迭代回溯法 思路是这样 红色框代表put 函数里的if没有通过 就不再有进一步迭代(子树...

Ink_cherry ⋅ 2017/05/16 ⋅ 0

开篇(2017-11-27)

故事很长,不知从何说起?(主编要催稿了-_-||,前方凑字,重点最后两段) 报考长春工业大学 当时选工大的时候,完全是出于一个目的:就是它离延边大学比较近。从此,便走了一条学霸路(伪学...

TinyDolphin ⋅ 2017/11/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 6分钟前 ⋅ 0

CentOS开机启动subversion

建立自启动脚本: vim /etc/init.d/subversion 输入如下内容: #!/bin/bash## subversion startup script for the server## chkconfig: 2345 90 10# description: start the subve......

随风而飘 ⋅ 9分钟前 ⋅ 0

Nginx + uwsgi @ubuntu

Nginx 安装 & 启动 sudo apt-get install nginx  #安装fnngj@ubuntu:~$ /etc/init.d/nginx start  #启动fnngj@ubuntu:~$ /etc/init.d/nginx stop  #关闭fnngj@ubuntu:~$ /etc/init.d/......

袁祾 ⋅ 10分钟前 ⋅ 0

版本控制工具

CSV , SVN , GIT ,VSS

颖伙虫 ⋅ 12分钟前 ⋅ 0

【2018.06.19学习笔记】【linux高级知识 13.1-13.3】

13.1 设置更改root密码 13.2 连接mysql 13.3 mysql常用命令

lgsxp ⋅ 20分钟前 ⋅ 0

LVM

LVM: 硬盘划分分区成物理卷->物理卷组成卷组->卷组划分逻辑分区。 1.磁盘分区: fdisk /dev/sdb 划分几个主分区 输入t更改每个分区类型为8e(LVM) 使用partprobe生成分区的文件:如/dev/sd...

ZHENG-JY ⋅ 48分钟前 ⋅ 0

彻底删除Microsoft Office的方法

参照此链接彻底删除Office https://support.office.com/zh-cn/article/%e4%bb%8e-pc-%e5%8d%b8%e8%bd%bd-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8?ui=zh-CN&rs=zh-CN&ad=CN......

Kampfer ⋅ 今天 ⋅ 0

大盘与个股之间关系

大盘走多:积极出手 顺势加码 大盘走空: 少量出手 退场观望 大盘做头:逆势减码 少量操作 大盘做底 : 小量建仓 小量试单

guozenhua ⋅ 今天 ⋅ 0

Day16 LVM(逻辑卷管理)与磁盘故障小案例

lvm详解 简述 LVM的产生是因为传统的分区一旦分区好后就无法在线扩充空间,也存在一些工具能实现在线扩充空间但是还是会面临数据损坏的风险;传统的分区当分区空间不足时,一般的解决办法是再...

杉下 ⋅ 今天 ⋅ 0

rsync实现多台linux服务器的文件同步

一、首先安装rsync,怎样安装都行,rpm,yum,还是你用源码安装都可以。因为我用的是阿里云的ESC,yum install rsync就ok了。 二、配置rsync服务 1.先建立个同步数据的帐号 123 groupadd r...

在下头真的很硬 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部