[Java]代碼    

package cn.xuhang.collection;

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

/**
 * 從一個點到達另一個點的路徑<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;//目標
	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/>
	 * 計算從S開始，沿著星號（*）前進，橫線（-）表示不可通過，到達E點的所有可行路徑。 <br/>
	 * 這里使用了深度優(yōu)先算法進行遍歷，從起點(0,0)開始，由于目標點所在的坐標在起點的右下方，所有優(yōu)先遍歷右邊和下邊的點。 <br/>
	 * 但是，這里也有例外，雖然目標點在起點右下方，但是在前進過程中仍然需要向左/上移動，比如： <br/>
	 * 		S - - - - <br/>
	 * 		* - * * * <br/>
	 * 		* - * - * <br/>
	 * 		* - E - * <br/>
	 * 		* - - - * <br/>
	 * 		* * * * * <br/>
	 * 每個點出發(fā)有四個方向可以移動，如果超出邊界則不移動，移動到下一個點之后如果這個點表示不可通過（-）則返回false。<br/>
	 * 每經(jīng)過一個點，會先將其放入path列表中，表示該點已經(jīng)走過，避免下一個點返回后重復(fù)造成死循環(huán)。比如A點向右移動到B點，B點可以向左移動到A點，
	 * 重復(fù)此步驟會造成死循環(huán)。因此需要一個列表記錄所走過的點，同時，在遍歷完該點四個方向的點之后表示遞歸這個點及該點之后所有可行路徑結(jié)束，從
	 * 列表中移除改點，從其他方向來的點可以繼續(xù)通過該點。
	 * 		* * -
	 * 		- A B
	 * 		- E F
	 * 比如經(jīng)過A點時，此時列表的變化依次是
	 * [*,*,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ù)走過的點造成死循環(huán)，參數(shù)path0用來記錄從起點開始到達每一個點之前的完整路徑。
	 * 
	 * @param grid 陣圖，一個二維數(shù)組，用不同的符號表示哪些點可以通過，哪些點不能通過，哪些點是目標所在的位置
	 * @param point 當前坐標，這里將坐標包裝成Point對象，對象有x,y兩個屬性，分別表示在二維數(shù)組中的位置
	 * @param path0 路徑，表示從起點開始，到達這個點之前所經(jīng)過的點的集合
	 * @return 表示這個點是否可以繼續(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);//拷貝上一個點經(jīng)過的路徑，并接著上一個點的路徑繼續(xù)
		
		if(grid[point.x][point.y] == 9){//到達
			pathes.add(p);
			return true;
		}
		
		if(grid[point.x][point.y] != 0 && !path.contains(point)){//這個點可以走(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，之后從其他點過來的也能繼續(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 +")";
		}
	}
}

標簽： 代碼

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