给定一个二维矩阵，找到从左上角到右下角的路径。 假设至少存在一条路径，您只需要找到一条有效路径即可。 您可以在任何位置向上、向右、向下、向左移动。

例如，给定

[1, 0, 0, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 0, 1]
[1, 0, 0, 0, 1]
[1, 0, 0, 0, 1]

一个有效的路径是

[1, 0, 0, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 0, 1]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 1]

Java 解决方案

public int[][] findPath(int[][] matrix){
	int m = matrix.length;
 
	int[][] result = new int[m][m];
 
	ArrayList<int[]> temp = new ArrayList<int[]>();
	ArrayList<int[]> list = new ArrayList<int[]>();
 
	dfs(matrix, 0, 0, temp, list);
 
 
	for(int i=0; i<list.size(); i++){
		result[list.get(i)[0]][list.get(i)[1]]=1;
		//System.out.println(Arrays.toString(list.get(i)));
	}
 
	result[0][0]=1;
 
	return result;
}
 
public void dfs(int[][] matrix, int i, int j, 
		ArrayList<int[]> temp,  ArrayList<int[]> list){
 
	int m=matrix.length;
 
	if(i==m-1 && j==m-1){
		list.clear();
		list.addAll(temp);
		return;
	}
 
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, 1, 0, -1};
 
	for(int k=0; k<4; k++){
		int x = i+dx[k];
		int y = j+dy[k];
 
		if(x>=0 && y>=0 && x<=m-1 && y<=m-1 && matrix[x][y]==1){
			temp.add(new int[]{x,y});
			int prev = matrix[x][y];
			matrix[x][y]=0;
 
			dfs(matrix, x, y, temp, list);
 
			matrix[x][y]=prev;
			temp.remove(temp.size()-1);
		}
	}		
}