企业🤖AI智能体构建引擎,智能编排和调试,一键部署,支持私有化部署方案 广告
## 多维空间上的搜索 问题提出:生活中地图无处不在,我们怎么快速寻找最近的酒店?怎么寻找一条迷宫的出路呢?怎么寻找一条到达目标的最短路径?等等 深度优先和广度优先的概念 深度优先搜索:在连通图中,从某一顶点出发,尝试去访问一个邻接的未被访问的顶点,若访问不到即退回上一个顶点,尝试去访问其他未被访问的顶点,若访问到了,即以该顶点为中心执行上述操作。直到没有顶点可访问为止。 广度优先搜索:在连通图中,从某一顶点出发,尝试去访问所有邻接的未被访问的顶点,接下来以这些顶点为中心去访问其邻接的未被访问的顶点。这样一层一层向外扩展,直到没有顶点可访问为止。 区别:在我看来,这两种搜索很像赛跑。为了知道几个同学谁跑步最快,我们有两种方法,第一种就是分别让每一个同学从起点跑到终点,统计每个同学的时间;这和深度优先搜索非常相似,深度优先搜索一味深入,只有无法再深入才返回寻找以他途径。第二种就是让所有同学一起跑,最先到达的就是最快的。这和广度非常相似,广度总是以某一点为中心向外扩张,有一种并发前进的意味,当然最先到达终点就是最快的。 多维空间上的搜索 无论在多少维的空间搜索,两种算法都是适用的,只是建立图的模型和算法的设计需要慎重考虑。 这里的多维空间指的是图的维数,九宫格就是属于二维的,还有翻箱子和三维的迷宫都是属于三维。这里只讨论二维和三维。 我们该怎么来完成我们的搜索呢? 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; } } ~~~