轉(zhuǎn)載https://www.cnblogs.com/wanghang-learning/p/9430672.html
一、問題介紹
有一個(gè)迷宮地圖，有一些可達(dá)的位置，也有一些不可達(dá)的位置（障礙、墻壁、邊界）。從一個(gè)位置到下一個(gè)位置只能通過向上（或者向右、或者向下、或者向左）走一步來實(shí)現(xiàn)，從起點(diǎn)出發(fā)，如何找到一條到達(dá)終點(diǎn)的通路。本文將用兩種不同的解決思路，四種具體實(shí)現(xiàn)來求解迷宮問題。
用二維矩陣來模擬迷宮地圖，1代表該位置不可達(dá)，0代表該位置可達(dá)。每走過一個(gè)位置就將地圖的對應(yīng)位置標(biāo)記，以免重復(fù)。找到通路后打印每一步的坐標(biāo)，最終到達(dá)終點(diǎn)位置。
封裝了點(diǎn)Dot，以及深度優(yōu)先遍歷用到的Block，廣度優(yōu)先遍歷用到的WideBlock。
private int[][] map = { //迷宮地圖,1代表墻壁，0代表通路
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
}; private int mapX = map.length - 1; //地圖xy邊界
private int mapY = map[0].length - 1; private int startX = 1; //起點(diǎn)
private int startY = 1; private int endX = mapX - 1; //終點(diǎn)
private int endY = mapY - 1;
//內(nèi)部類，封裝一個(gè)點(diǎn)
public class Dot{
private int x; //行標(biāo)
private int y; //列標(biāo)
public Dot(int x , int y) {
this.x = x;
this.y = y;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
}
//內(nèi)部類，封裝走過的每一個(gè)點(diǎn),自帶方向
public class Block extends Dot{
private int dir; //方向,1向上，2向右，3向下，4向左
public Block(int x , int y) {
super(x , y);
dir = 1;
}
public int getDir(){
return dir;
}
public void changeDir(){
dir++;
}
}
/*
廣度優(yōu)先遍歷用到的數(shù)據(jù)結(jié)構(gòu)，它需要一個(gè)指向父節(jié)點(diǎn)的索引
*/
public class WideBlock extends Dot{
private WideBlock parent;
public WideBlock(int x , int y , WideBlock p){
super(x , y);
parent = p;
}
public WideBlock getParent(){
return parent;
}
}</pre>
二、回溯法
思路：從每一個(gè)位置出發(fā)，下一步都有四種選擇（上右下左），先選擇一個(gè)方向，如果該方向能夠走下去，那么就往這個(gè)方向走，當(dāng)前位置切換為下一個(gè)位置。如果不能走，那么換個(gè)方向走，如果所有方向都走不了，那么退出當(dāng)前位置，到上一步的位置去，當(dāng)前位置切換為上一步的位置。一致這樣執(zhí)行下去，如果當(dāng)前位置是終點(diǎn)，那么結(jié)束。如果走過了所有的路徑都沒能到達(dá)終點(diǎn)，那么無解。下面看代碼
private Stack<Block> stack = new Stack<Block>(); //回溯法存儲路徑的棧
public void findPath1(){
Block b = new Block(startX,startY);
stack.push(b); //起點(diǎn)進(jìn)棧
while(!stack.empty()){ //?？沾硭新窂揭炎咄?，沒有找到通路
Block t = stack.peek(); int x = t.getX(); //獲取棧頂元素的x
int y = t.getY(); //獲取棧頂元素的y
int dir = t.getDir(); //獲取棧頂元素的下一步方向
map[x][y] = 1; //把地圖上對應(yīng)的位置標(biāo)記為1表示是當(dāng)前路徑上的位置，防止往回走
if(t.getX() == endX && t.getY() == endY) {//已達(dá)終點(diǎn)
return ;
} switch(dir){ case 1: //向上走一步
if(x - 1 >= 0 && map[x - 1][y] == 0){ //判斷向上走一步是否出界&&判斷向上走一步的那個(gè)位置是否可達(dá)
stack.push(new Block(x - 1 , y)); //記錄該位置
}
t.changeDir(); //改變方向，當(dāng)前方向已走過
continue; //進(jìn)入下一輪循環(huán)
case 2: if(y + 1 <= mapY && map[x][y+1] == 0){
stack.push(new Block(x , y + 1));
}
t.changeDir(); continue; case 3: if(x + 1 <= mapX && map[x+1][y] == 0){
stack.push(new Block(x + 1 , y));
}
t.changeDir(); continue; case 4: if(y - 1 >= 0 && map[x][y - 1] == 0){
stack.push(new Block(x , y - 1));
}
t.changeDir(); continue;
}
t = stack.pop(); //dir > 4 當(dāng)前Block節(jié)點(diǎn)已經(jīng)沒有方向可走,出棧
map[t.getX()][t.getY()] = 0; //出棧元素對應(yīng)的位置已經(jīng)不再當(dāng)前路徑上，表示可達(dá)
}
} //打印棧
public void printStack(){ int count = 1;
while(!stack.empty()){
Block b = stack.pop();
System.out.print("(" + b.getX() + "," + b.getY() + ") ");
if(count % 10 == 0)
System.out.println("");
count++;
}
}
遞歸實(shí)現(xiàn)：
private Stack<Block> s = new Stack<Block>(); //回溯法全局輔助棧
private Stack<Block> stack = new Stack<Block>(); //回溯法存儲路徑的棧
public void findPath2(){ if(startX >= 0 && startX <= mapX && startY >= 0 && startY <= mapY && map[startX][startY] == 0){
find(startX , startY);
}
} private void find(int x , int y){
map[x][y] = 1; if(x == endX && y == endY) {
s.push(new Block(x , y)); while(!s.empty()){
stack.push(s.pop());
} //return ; //在此處返回會使后續(xù)遞歸再次尋找路線會經(jīng)過這里，如果不返回，整個(gè)函數(shù)執(zhí)行完畢，所有路徑都會被訪問到
}
s.push(new Block(x , y));if( x - 1 >= 0 && map[x - 1][y] == 0 ){ //可以往上走，那么往上走
find(x - 1 , y);
} if(x + 1 <= mapX && map[x + 1][y] == 0){ //可以往下走，那么往下走
find(x + 1 , y);
} if(y - 1 >= 0 && map[x][y - 1] ==0){ //往左
find(x , y - 1);
} if(y + 1 <= mapY && map[x][y + 1] == 0){
find(x , y + 1);
} if(!s.empty()){
s.pop();
}
}
三、深度優(yōu)先遍歷
思路：和上面的回溯法思想基本一樣，能向某個(gè)方向走下去就一直向那個(gè)方向走，不能走就切換方向，所有方向都不能走了就回到上一層位置。
private Stack<Dot> stackDeep = new Stack<Dot>(); //深度遍歷時(shí)用的存儲棧
private Stack<Dot> sDeep = new Stack<Dot>(); //深度遍歷時(shí)用到的輔助棧
public void findPath3() { // 判斷起點(diǎn)的合法性
if (startX >= 0 && startX <= mapX && startY >= 0 && startY <= mapY && map[startX][startY] == 0) {
deepFirst(startX, startY);
}
} public void deepFirst(int x, int y) {
Dot b = new Dot(x, y);
sDeep.push(b);
map[x][y] = 1; // 標(biāo)記已訪問 if (x == endX && y == endY) { while (!sDeep.empty()) {
stackDeep.push(sDeep.pop());
} //return ; //此處的return和上一個(gè)遞歸的return一樣,如果返回
}
for (int i = 1; i <= 4; i++) { // 在每個(gè)方向上進(jìn)行嘗試
if (i == 1) { // 上
if (x - 1 >= 0 && map[x - 1][y] == 0) {
deepFirst(x - 1, y);
}
} else if (i == 2) { // 右
if (y + 1 <= mapY && map[x][y + 1] == 0) {
deepFirst(x, y + 1);
}
} else if (i == 3) { // 下
if (x + 1 <= mapX && map[x + 1][y] == 0) {
deepFirst(x + 1, y);
}
} else { // 左
if (y - 1 >= 0 && map[x][y - 1] == 0) {
deepFirst(x, y - 1);
}
}
} if(!sDeep.empty()) {
sDeep.pop(); // 四個(gè)方向都已嘗試過，并且沒成功，退棧
}
} //打印深度優(yōu)先遍歷的棧
public void printDeepStack(){ int count = 1; while(!stackDeep.empty()){
Dot b = stackDeep.pop();
System.out.print("(" + b.getX() + "," + b.getY() + ") "); if(count++ % 10 == 0){
System.out.println("");
}
}
}
棧實(shí)現(xiàn)、遞歸和深度優(yōu)先遍歷，這三者的執(zhí)行思路是一樣的，都可以看做二叉樹先根遍歷的變體，起點(diǎn)看做根節(jié)點(diǎn)，每個(gè)選擇方向看做一個(gè)分叉，四個(gè)方向?qū)?yīng)四個(gè)子節(jié)點(diǎn)，如果某個(gè)節(jié)點(diǎn)四個(gè)方向都走不了，那么它就是葉子節(jié)點(diǎn)。每走到一個(gè)葉子節(jié)點(diǎn)就是一條完整的執(zhí)行路徑，只不過不一定到達(dá)了終點(diǎn)。按照先根遍歷的方式，最終會走完每一條路徑，如果在路徑中找到了終點(diǎn)，那么記錄下這條路徑線索。二叉樹先根遍歷的遞歸實(shí)現(xiàn)對應(yīng)了上面的遞歸實(shí)現(xiàn)，只不過這里是四叉樹，棧實(shí)現(xiàn)可以看成先根遍歷的非遞歸算法，而深度優(yōu)先遍歷和先跟遍歷本就有異曲同工之妙。
四、廣度優(yōu)先遍歷
思路：這種方法和前面三種是不同的思路。先從根節(jié)點(diǎn)出發(fā)，將當(dāng)前節(jié)點(diǎn)的所有可達(dá)子節(jié)點(diǎn)依次訪問，在依次訪問子節(jié)點(diǎn)的子節(jié)點(diǎn)，一直下去直到所有節(jié)點(diǎn)被遍歷。
private WideBlock wb; //廣度遍歷的終點(diǎn)節(jié)點(diǎn)
/* 廣度優(yōu)先遍歷 */
public void findPath4(){
wideFirst();
} public void wideFirst(){
WideBlock start = new WideBlock(startX , startY , null);
Queue<WideBlock> q = new LinkedList<WideBlock>();
map[startX][startY] = 1;
q.offer(start); while(q.peek() != null){
WideBlock b = q.poll(); int x = b.getX(); int y = b.getY(); if(x == endX && y == endY){ //判斷當(dāng)前節(jié)點(diǎn)是否已達(dá)終點(diǎn)
wb = b; return;
} if (x - 1 >= 0 && map[x - 1][y] == 0) { //判斷當(dāng)前節(jié)點(diǎn)的能否向上走一步，如果能，則將下一步節(jié)點(diǎn)加入隊(duì)列
q.offer(new WideBlock(x - 1 , y , b)); //子節(jié)點(diǎn)入隊(duì)
map[x - 1][y] = 1; //標(biāo)記已訪問
} if (y + 1 <= mapY && map[x][y + 1] == 0) { //判斷當(dāng)前節(jié)點(diǎn)能否向右走一步
q.offer(new WideBlock(x , y + 1 , b));
map[x][y + 1] = 1;
} if (x + 1 <= mapX && map[x + 1][y] == 0) {
q.offer(new WideBlock(x + 1 , y , b));
map[x + 1][y] = 1;
} if (y - 1 >= 0 && map[x][y - 1] == 0) {
q.offer(new WideBlock(x , y - 1 , b));
map[x][y -1] = 1;
}
}
} //打印廣度遍歷的路徑
public void printWidePath(){
WideBlock b = wb; int count = 1; while(b != null){
System.out.print("(" + b.getX() + "," + b.getY() + ") ");
b = b.getParent(); if(count++ % 10 == 0){
System.out.println("");
}
}
}
