## 多维空间上的搜索
问题提出：生活中地图无处不在，我们怎么快速寻找最近的酒店？怎么寻找一条迷宫的出路呢？怎么寻找一条到达目标的最短路径？等等
深度优先和广度优先的概念
深度优先搜索：在连通图中，从某一顶点出发，尝试去访问一个邻接的未被访问的顶点，若访问不到即退回上一个顶点，尝试去访问其他未被访问的顶点，若访问到了，即以该顶点为中心执行上述操作。直到没有顶点可访问为止。
广度优先搜索：在连通图中，从某一顶点出发，尝试去访问所有邻接的未被访问的顶点，接下来以这些顶点为中心去访问其邻接的未被访问的顶点。这样一层一层向外扩展，直到没有顶点可访问为止。
区别：在我看来，这两种搜索很像赛跑。为了知道几个同学谁跑步最快，我们有两种方法，第一种就是分别让每一个同学从起点跑到终点，统计每个同学的时间；这和深度优先搜索非常相似，深度优先搜索一味深入，只有无法再深入才返回寻找以他途径。第二种就是让所有同学一起跑，最先到达的就是最快的。这和广度非常相似，广度总是以某一点为中心向外扩张，有一种并发前进的意味，当然最先到达终点就是最快的。
多维空间上的搜索
无论在多少维的空间搜索，两种算法都是适用的，只是建立图的模型和算法的设计需要慎重考虑。
这里的多维空间指的是图的维数，九宫格就是属于二维的，还有翻箱子和三维的迷宫都是属于三维。这里只讨论二维和三维。
我们该怎么来完成我们的搜索呢？
1. 首先我们应该设计恰当的地图，一般来说我们可以用二维数组来模拟二维地图，用三维数组来模拟三维地图。
2. 其次设计恰当的搜索算法，尽可能以最快最方便的方法完成搜索过程，达到我们需要的结果。
我们还是从实践中理解算法吧。
22657: 迷宫(maze)
题目描述
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式。保证起点上没有障碍。
输入
第一行N、M和T，N为行，M为列，T为障碍总数。
第二行起点坐标SX,SY，终点坐标FX,FY。
接下来T行，每行为障碍的坐标。
输出
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
代码：
packageacm练习;
importjava.util.Scanner;
importjava.util.Stack;
/**
*
* @author 林志伟 给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，
* 问每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四 种方式。保证起点上没有障碍。
* 解法：采用深度优先搜索寻找从起点搜索到达终点的路径
*
*/
publicclass Main22657 {
// 该数组保存了某一点向上下左右时坐标应该执行的操作
static int direct[][] = { { -1, 0 }, { 1,0 }, { 0, -1 }, { 0, 1 } };
static int n = 0, m = 0, t, sx, sy, fx,fy, tx, ty;
static int map[][] = null;
public static void main(String[] args) {
Scanner in = newScanner(System.in);
// 上下左右
while (in.hasNext()) {
n = in.nextInt();
m = in.nextInt();
t= in.nextInt();
/**
* 建图：0:表示可以通过，1 ：表示障碍
*/
map = new int[n][m];
sx = in.nextInt() - 1;
sy = in.nextInt() - 1;
map[sx][sy] = 2;
fx = in.nextInt() - 1;
fy = in.nextInt() - 1;
map[fx][fy] = 3;
for(int i = 0; i < t; i++) {
tx = in.nextInt() - 1;
ty = in.nextInt() -1;
map[tx][ty] = 1;
}
/**
* 开始搜索
*/
int res = dfs();
// 输出结果
System.out.println(res);
}
}
public static int dfs() {
Stack<Point> stacks = newStack<Point>();
// 起点
Point startpoint = new Point(sx,sy);
stacks.push(startpoint);
map[sx][sy] = 1;
Point curpoint, tpoint = null;
int road;
int res = 0;
while (!stacks.isEmpty()) {
curpoint = stacks.peek();
// 判断是否到达终点,到了返回继续寻找另一条路
if (curpoint.x == fx&& curpoint.y == fy) {
res++;
stacks.pop();
map[tpoint.x][tpoint.y]= 0;
continue;
}
road = curpoint.getRoad();
if (road == -1) {
// 返回寻找另一条路
tpoint =stacks.pop();
map[tpoint.x][tpoint.y]= 0;
continue;
} else {
tx = curpoint.x +direct[road][0];
ty = curpoint.y +direct[road][1];
// 判断该路是否可走
if (tx >= 0&& tx < n && ty >= 0 && ty < m &&map[tx][ty] != 1) {
// 可走的路
tpoint = newPoint(tx, ty);
stacks.push(tpoint);
map[tx][ty] =1;
continue;
}
}
}
return res;
}
}
/**
*
* @author 林志伟 点类：保存某一个顶点的坐标以及哪些方向是否被访问过
*/
classPoint {
Point(int x, int y) {
this.x = x;
this.y = y;
}
int x;
int y;
// 表示某个方向走过了没有
boolean isRun[] = new boolean[4];
public int getRoad() {
for (int i = 0; i < 4; i++) {
if (isRun[i] ==false) {
isRun[i]= true;
return i;
}
}
return -1;
}
}
问题 C : G. 翻箱子
题目描述
丁丁最近喜欢玩一种小游戏，叫翻箱子，玩得非常着迷，可时当当却笑他说这个游戏很久很久以前他就玩过并且早就通关了，这让丁丁好不爽，他也想马上通关，你能帮帮他吗？这个游戏有很多关，每一关都是一个地图，箱子是1×2×1大小的，如果箱子是平躺的，那么箱子可以往前或往后滚动，或者在两端竖起来，如果箱子是竖起来的，它可以往四方向倒下，目标就是使箱子竖着到达地图上有坑的地方，这样才能进入下一局，箱子只能全部在白色的格子中翻动，只要有一部分不在白色格子，游戏将失败。如下图，第一张图是开局图，第二张图是箱子往右倒下的图，第三张图是箱子往下滚动的图，第四张图是经过若干步骤后到达的位置，下一步，只要把箱子立起来，就能够让箱子到达目标坑位，进入下一关卡。
代码：
~~~
package 程序设计竞赛决赛;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/***
* @author 林志伟
* 问题 C : G. 翻箱子 传统的九宫格放上面的棋子都只有一种状态，因此用二维的地图就可以进行搜索，
* 而在该题中箱子却有着三种状态，竖着，横躺，竖躺，因此必须构三维的地图模型
* 三维地图模型介绍：该地图由三张二维地图构成，每一张二维地图代表着一种状态，
* 在地图上 # 表示障碍 . 表示未被访问 * 表示已访问
*
*/
public class MainC {
// 二维地图，三维地图
static char map2d[][]= null, map3d[][][] = null;
// 三维数组：第一维确定箱子的状态，第二维确定方向，第三维确定 坐标和状态的变化
static intdirect[][][] = {
{ { -1,0, 0 }, { 1, 0, 0 }, { 0, -1, 2 }, { 0, 2, 2 } },
{ { -1,0, 1 }, { 2, 0, 1 }, { 0, -1, 0 }, { 0, 1, 0 } },
{ { -2,0, -1 }, { 1, 0, -1 }, { 0, -2, -2 }, { 0, 1, -2 } } };
static int m, n, i, j,k, h;
// 保存开始的箱子，和终点的箱子
static Box beginbox =null, endbox = null;
public static voidmain(String[] args) {
Scanner in =new Scanner(System.in);
String temp;
while(in.hasNext()) {
m =in.nextInt();
n =in.nextInt();
map2d =new char[m][n];
map3d =new char[m][n][3];
// 保存二维地图
for (i =0; i < m; i++) {
temp= in.next();
for(j = 0; j < temp.length(); j++) {
map2d[i][j]= temp.charAt(j);
}
}
// 把二维地图转化为三维地图
change2Dto3D();
// 开始广度搜索
int res= bfs();
//输出结果
if (res== 1) {
System.out.println("noway");
} else {
System.out.println(res);
}
}
}
/**
* 从起点广度优先搜索搜索终点
* @return
* -1：表示搜索不到终点
* 不为-1：表示最短步数
*/
public static int bfs() {
Queue<Box>queue = new LinkedList<Box>();
queue.add(beginbox);
Box tempbox,box;
int x, y, s;
int res = -1;
//当搜索到终点或队列为空停止搜索
while (!queue.isEmpty()){
tempbox= queue.remove();
//判断是否到达终点，若到达跳出循环，否则继续搜索
if(tempbox.x == endbox.x && tempbox.y == endbox.y
&&tempbox.status == endbox.status) {
res= tempbox.step;
break;
}
// 尝试搜索四个方向，把无法前进的方向剔除掉
for (int i = 0; i < 4; i++) {
x= direct[tempbox.status][i][0] + tempbox.x;
y =direct[tempbox.status][i][1] + tempbox.y;
s= direct[tempbox.status][i][2] + tempbox.status;
//判断是哪种类型的箱子
if(s == 0) {
if(x >= 0 && x < m && y >= 0 && y < n - 1
&&map3d[x][y][0] == '.'
&&map3d[x][y + 1][0] != '#') {
box= new Box(x, y, s);
box.step= tempbox.step + 1;
queue.add(box);
map3d[x][y][0]= '*';
}
}
if(s == 1) {
if(x >= 0 && x < m - 1 && y >= 0 && y < n
&&map3d[x][y][1] == '.'
&&map3d[x + 1][y][1] != '#') {
box= new Box(x, y, s);
box.step= tempbox.step + 1;
queue.add(box);
map3d[x][y][1]= '*';
}
}
if(s == 2) {
if(x >= 0 && x < m && y >= 0 && y < n
&&map3d[x][y][2] == '.') {
box= new Box(x, y, s);
box.step= tempbox.step + 1;
queue.add(box);
map3d[x][y][2]= '*';
}
}
}
}
return res;
}
/**
*将2d的地图转化为3d地图
**/
public static voidchange2Dto3D() {
boolean is = true;
for (i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
for(h = 0; h < 3; h++) {
map3d[i][j][h]= '.';
}
if(map2d[i][j] == '#') {
for (k = 0; k < 3; k++) {
map3d[i][j][k]= '#';
}
}
//创建终点箱子
if(map2d[i][j] == 'H') {
//只有竖着状态才能进入小洞
endbox= new Box(i, j, 2);
}
//创建起点箱子
if(map2d[i][j] == 'X' && is) {
//横躺
if(j + 1 < n && map2d[i][j + 1] == 'X') {
beginbox= new Box(i, j, 0);
map3d[i][j][0]= '*';
}else
//竖躺
if(i + 1 < m && map2d[i + 1][j] == 'X') {
beginbox= new Box(i, j, 1);
map3d[i][j][1]= '*';
}else {
// 竖着
beginbox= new Box(i, j, 2);
map3d[i][j][2]= '*';
}
is= false;
}
}
}
}
}
/**
*
* @author 林志伟
* 箱子类：保存箱子的坐标，状态
*/
class Box {
// 0表示横躺 1表示竖躺 2表示竖着
int status = -1;
int x, y;
int step;
/**
*
* @param x 横坐标
* @param y 纵坐标
* @param status 状态
*/
Box(int x, int y, intstatus) {
this.x = x;
this.y = y;
step = 0;
this.status =status;
}
}
~~~
- 我的笔记
- 服务器
- ubuntu svn 环境的搭建
- ubuntu Memcache 的配置
- ubuntu 密钥登录服务器
- centos 搭建服务器环境
- nginx+tomcat 集群搭建
- 餐厅运营来看如何构建高性能服务器
- VMware-Centos-网络配置
- Ubuntu-PHP-Apache-Mysql-PhpMyadmin的搭建
- UbuntuApache配置日志
- linux获取当前执行脚本的目录
- Ubuntu svn的快速配置（原创）
- Https配置
- Mysql 不支持远程连接解决方案
- ubuntu+apache+rewrite
- php Mcrypt 扩展
- 重启Apache出现警告信息Could not reliably determine the server's fully qualified domain name,
- Mysql无法远程连接
- 定时任务设置
- Linux中Cache内存占用过高解决办法
- Ubuntu14-04安装redis和php5-redis扩展
- php
- thinkphp3.2 一站多城市配置
- PHP 安全编程建议(转)
- phpexcel导入时间处理
- Mysql按时，天，月，年统计数据
- PHP-支付宝-APP支付
- 百度爬虫-获取全国数据
- PHPEXCEL导入导出excel文件
- php-微信app支付后端设计
- Phpqrcode生成二维码
- 图片+文字水印
- 数据库优化
- java
- Mybatis 二级缓存
- 微信
- 微信公众号多域名授权
- 微信扫码支付
- web
- 网站性能优化方案实施
- ionic环境搭建
- 登录设计方案
- 设置dev元素的宽高比例
- 设计模式
- app
- 版本更新
- 微擎数据库操作扩展
- select
- find
- delete
- update
- insert
- where
- order
- page
- group
- having
- limit
- fields
- debug
- bind
- join
- alias
- query
- 聚合函数
- count
- sum
- max
- min
- avg
- 事务管理
- 自增自减
- 算法设计
- ACM:入口的选择------深度优先搜索
- java:N的N次方
- 最少拦截系统:贪心思想
- ACM:蚕宝宝：搜索
- ACM:n!的位数 :斯特林公式
- 神奇的异或
- 中国剩余定理
- 矩阵翻硬币
- 回溯法
- ACM程序设计网站集锦
- 博弈论
- 多维空间上的搜索算法
- 算法学习笔记之一（排序）
- 算法学习笔记之二（堆排序）
- 算法学习笔记之三（快速排序）
- ACM俱乐部密码
- 原创开源
- 个人感悟