迷宫问题 [No. 8]

问题：

在一个n*m的迷宫里,每一个坐标点有两种可能: 0 或 1。0表示该位置允许通过,1表示该位置不允许通过。从坐标(0,0)点出发，找出所有通往出口(n-1, m-1) 的路径。

如果我们用二维矩阵来表示，那么地图可以表示成：

0 0 0 0 0
1 0 1 0 1
0 0 0 01
0 1 0 0 0
0 0 0 1 0

在上面一个例子里，其中一条路径为0,0 -> 0,1 -> 0,2 -> 0,3 -> 1, 3 -> 2, 3 ->3, 3 -> 3, 4 -> 4,4

分析：

假设我们到了点 （i, j）， 如果这个点不是 1， 那么，我们可以继续向右边走，即到点（i, j+1），也可以往下走，即到点 （i+1, j）, 向左（i, j-1）,向上（i -1, j）。对于这样每一个点，什么时候不再“前进”了呢？

1、这个点已经超出了矩阵的范围；

2、这个点值为 1；

3、这个点是终点。

4、这个点已经被遍历了。

如果这个点是终点，我们把路径上经历过的点都打印出来，所以，我们需要一个存储所有点的一个数据结构，这里，我们使用ArrayList.

PS.其实这个问题与打印一个二叉树所有路径的问题本质上是一模一样的（参考：http://blog.csdn.net/beiyeqingteng/article/details/7060642）。

实现代码如下：

public class Maze {
	
	public void findPath(int[][] array, ArrayList<String> visited, int length2, ArrayList<Point> list, int length, int i, int j) {
		//exit 
		if (i >= array.length || j >= array[0].length || i < 0 || j < 0 || array[i][j] == 1 ||  visited(visited, length2, i, j)== true) {
			return;
		}
		//add the point to list
		list.add(length, new Point(i, j));
		++length;
		
		visited.add(length2, i+","+j);
		++length2;
		
		//we find the exit, and print all the points on the path
		if (i == array.length - 1 && j == array[0].length - 1) {
			print(list, length);
		}
		// the right direction	
		findPath(array, visited, length2, list, length, i, j+1);
		// the down direction
		findPath(array, visited, length2, list, length, i+1, j);	
		// the left direction
		findPath(array, visited, length2, list, length, i, j-1);
		// the up direction
		findPath(array, visited, length2, list, length, i-1, j);
	}
	// check whether the point has been visited or not
	public boolean visited(ArrayList<String> visited, int length2, int i, int j) {
		String point = i+","+j;
		for (int k = 0; k < length2; k++) {
			if (visited.get(k).equals(point)) return true;
		}
		return false;
	}
	
	public void print(ArrayList<Point> list, int length) {
		for (int i = 0; i < length; i++) {
			System.out.println(list.get(i).getX()+","+list.get(i).getY());
		}
		System.out.println("---------------------------");
	}
	
	public static void main(String[] args) {
		int[][] array = {{0,0, 0}, {0,0, 0}};
		Maze maze = new Maze();
		ArrayList<Point> list = new ArrayList<Point>();
		ArrayList<String> visited = new ArrayList<String>();
		maze.findPath(array, visited, 0, list, 0, 0, 0);
	}
}

class Point {
	int x = 0;
	int y = 0;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
}

扩展：

只找出所有路径里最短的一条？

答案：我们可以设置一个全局变量保存当前最短路径，只需要把所有可行的路径进行比较，我们就可以找到最短的路径。

转载请注明出处：blog.csdn.net/beiyeqingteng

其实这个问题与打印一个二叉树所有路径的问题本质上是一模一样（参考：http://blog.csdn.net/beiyeqingteng/article/details/7060642）。