[Java]代碼    

package cn.xuhang.collection;

import java.util.ArrayList;
import java.util.List;

/**
 * 從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)的路徑<br/>
 * 用到深度優(yōu)先算法dfs<br/>
 * 
 * @author Hang
 *
 */
public class MazePath{
	public static List<Point> path = new ArrayList<Point>();
	public static List<List<Point>> pathes = new ArrayList<List<Point>>();
	public static int block = 0;//不可通過
	public static int access = 1;//可以通過
	public static int target = 9;//目標(biāo)
	public static void main(String[] args) {
		int[][] grid = {{1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1},
						{0,1,1,1,1,0,0,0,1,0,1,0,1,0,1,1,1},
						{1,0,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1},
						{1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0},
						{1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0},
						{1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1},
						{1,0,1,1,0,0,0,1,9,0,0,1,1,1,0,0,1},
						{1,0,1,0,0,1,0,1,1,0,0,0,1,1,1,0,1},
						{1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0},
						{1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0},
						{1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,0},
						{1,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1},
						{0,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,1},
						{1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1}};
		
		dfs(grid, new Point(0, 0), path);
		if(pathes.size() > 0){
			for(List<Point> posibility : pathes){
				System.out.println("============");
				System.out.println(posibility);
			}
		}
	}
	/**
	 * 
	 * 		S * * * * <br/>
	 * 		* - * - - <br/>
	 * 		- - * - - <br/>
	 * 		* * * - - <br/>
	 * 		- * - * - <br/>
	 * 		* E * * - <br/>
	 * 計(jì)算從S開始，沿著星號(hào)（*）前進(jìn)，橫線（-）表示不可通過，到達(dá)E點(diǎn)的所有可行路徑。 <br/>
	 * 這里使用了深度優(yōu)先算法進(jìn)行遍歷，從起點(diǎn)(0,0)開始，由于目標(biāo)點(diǎn)所在的坐標(biāo)在起點(diǎn)的右下方，所有優(yōu)先遍歷右邊和下邊的點(diǎn)。 <br/>
	 * 但是，這里也有例外，雖然目標(biāo)點(diǎn)在起點(diǎn)右下方，但是在前進(jìn)過程中仍然需要向左/上移動(dòng)，比如： <br/>
	 * 		S - - - - <br/>
	 * 		* - * * * <br/>
	 * 		* - * - * <br/>
	 * 		* - E - * <br/>
	 * 		* - - - * <br/>
	 * 		* * * * * <br/>
	 * 每個(gè)點(diǎn)出發(fā)有四個(gè)方向可以移動(dòng)，如果超出邊界則不移動(dòng)，移動(dòng)到下一個(gè)點(diǎn)之后如果這個(gè)點(diǎn)表示不可通過（-）則返回false。<br/>
	 * 每經(jīng)過一個(gè)點(diǎn)，會(huì)先將其放入path列表中，表示該點(diǎn)已經(jīng)走過，避免下一個(gè)點(diǎn)返回后重復(fù)造成死循環(huán)。比如A點(diǎn)向右移動(dòng)到B點(diǎn)，B點(diǎn)可以向左移動(dòng)到A點(diǎn)，
	 * 重復(fù)此步驟會(huì)造成死循環(huán)。因此需要一個(gè)列表記錄所走過的點(diǎn)，同時(shí)，在遍歷完該點(diǎn)四個(gè)方向的點(diǎn)之后表示遞歸這個(gè)點(diǎn)及該點(diǎn)之后所有可行路徑結(jié)束，從
	 * 列表中移除改點(diǎn)，從其他方向來的點(diǎn)可以繼續(xù)通過該點(diǎn)。
	 * 		* * -
	 * 		- A B
	 * 		- E F
	 * 比如經(jīng)過A點(diǎn)時(shí)，此時(shí)列表的變化依次是
	 * [*,*,A]→[*,*,A,E]→[*,*,A,E,F]→[*,*,A,E,F,B]→[*,*,A,E,F]→[*,*,A,E]→
	 * [*,*,A]→[*,*,A,B]→[*,*,A,B,F]→[*,*,A,B,F,E]→[*,*,A,B,F]→[*,*,A,B]→[*,*,A]→[*,*]
	 * 
	 * path列表用來防止重復(fù)走過的點(diǎn)造成死循環(huán)，參數(shù)path0用來記錄從起點(diǎn)開始到達(dá)每一個(gè)點(diǎn)之前的完整路徑。
	 * 
	 * @param grid 陣圖，一個(gè)二維數(shù)組，用不同的符號(hào)表示哪些點(diǎn)可以通過，哪些點(diǎn)不能通過，哪些點(diǎn)是目標(biāo)所在的位置
	 * @param point 當(dāng)前坐標(biāo)，這里將坐標(biāo)包裝成Point對(duì)象，對(duì)象有x,y兩個(gè)屬性，分別表示在二維數(shù)組中的位置
	 * @param path0 路徑，表示從起點(diǎn)開始，到達(dá)這個(gè)點(diǎn)之前所經(jīng)過的點(diǎn)的集合
	 * @return 表示這個(gè)點(diǎn)是否可以繼續(xù)往下走，這里獲取可行的路徑{@link pathes}是主要目的，返回值沒有太大作用
	 */
	public static boolean dfs(int[][] grid, Point point, List<Point> path0){
		
		List<Point> p = new ArrayList<Point>();
		p.addAll(path0);
		p.add(point);//拷貝上一個(gè)點(diǎn)經(jīng)過的路徑，并接著上一個(gè)點(diǎn)的路徑繼續(xù)
		
		if(grid[point.x][point.y] == 9){//到達(dá)
			pathes.add(p);
			return true;
		}
		
		if(grid[point.x][point.y] != 0 && !path.contains(point)){//這個(gè)點(diǎn)可以走(1和9) 并且 未走過
			path.add(point);//現(xiàn)在走point
			if(point.x + 1 <= grid.length-1){
				dfs(grid, point.down(), p);						//往下
			}
			if(point.y + 1 <= grid[point.x].length-1){
				dfs(grid, point.right(), p);					//往右
			}
			if(point.x - 1 >= 0){
				dfs(grid, point.up(), p);						//往上
			}
			if(point.y - 1 >= 0){
				dfs(grid, point.left(), p);						//往左
			}
			path.remove(point);//走過point，之后從其他點(diǎn)過來的也能繼續(xù)走
		}
		//如果不可走(0) 或者 已走過
		return false;
	}
	
	
	static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		Point left(){
			return new Point(x, y-1);
		}
		Point right(){
			return new Point(x, y+1);
		}
		Point up(){
			return new Point(x-1, y);
		}
		Point down(){
			return new Point(x+1, y);
		}
		
		public String printDirection(Point nextPoint){
			String direction = null;
			if(nextPoint == null){
				direction = "●";
			}else{
				if(this.x == nextPoint.x){
					direction = (this.y < nextPoint.y) ? "→" : "←";
				}
				if(this.y == nextPoint.y){
					direction = (this.x < nextPoint.x) ? "↓" : "↑";
				}
			}
			return direction;
		}
		
		@Override
		public int hashCode() {
			return super.hashCode();
		};
		@Override
		public boolean equals(Object obj){
			Point p = (Point) obj;
			if(p.x == this.x && p.y == this.y){
				return true;
			}else{
				return false;
			}
		}
		@Override
		public String toString() {
			return "(" + this.x + "," + this.y +")";
		}
	}
}

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。