## 多維空間上的搜索 問題提出：生活中地圖無處不在，我們怎么快速尋找最近的酒店？怎么尋找一條迷宮的出路呢？怎么尋找一條到達目標的最短路徑？等等 深度優先和廣度優先的概念 深度優先搜索：在連通圖中，從某一頂點出發，嘗試去訪問一個鄰接的未被訪問的頂點，若訪問不到即退回上一個頂點，嘗試去訪問其他未被訪問的頂點，若訪問到了，即以該頂點為中心執行上述操作。直到沒有頂點可訪問為止。 廣度優先搜索：在連通圖中，從某一頂點出發，嘗試去訪問所有鄰接的未被訪問的頂點，接下來以這些頂點為中心去訪問其鄰接的未被訪問的頂點。這樣一層一層向外擴展，直到沒有頂點可訪問為止。 區別：在我看來，這兩種搜索很像賽跑。為了知道幾個同學誰跑步最快，我們有兩種方法，第一種就是分別讓每一個同學從起點跑到終點，統計每個同學的時間；這和深度優先搜索非常相似，深度優先搜索一味深入，只有無法再深入才返回尋找以他途徑。第二種就是讓所有同學一起跑，最先到達的就是最快的。這和廣度非常相似，廣度總是以某一點為中心向外擴張，有一種并發前進的意味，當然最先到達終點就是最快的。 多維空間上的搜索 無論在多少維的空間搜索，兩種算法都是適用的，只是建立圖的模型和算法的設計需要慎重考慮。 這里的多維空間指的是圖的維數，九宮格就是屬于二維的，還有翻箱子和三維的迷宮都是屬于三維。這里只討論二維和三維。 我們該怎么來完成我們的搜索呢？ 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; } } ~~~