题解 | #矩阵中的路径#

import java.util.*;

public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型二维数组 * @param word string字符串 * @return bool布尔型 */ public boolean hasPath (char[][] matrix, String word) { int len = matrix.length; int len1 = matrix[0].length; boolean[][] is_pass = new boolean[len][len1]; char first = word.charAt(0);

	boolean flag = false;
	label:for(int i = 0;i < len;i++) {
    	for(int j = 0;j < len1;j++) {
    		if(first == matrix[i][j]) {
    			if(!flag) {
    				is_pass[i][j] = true;
    				flag = func(matrix,word.substring(1),is_pass,i,j);
    			}
    		}
    		if(flag) break label;
            else clear(is_pass);
    	}
    }
	
	return flag;
}

public boolean func(char[][] matrix, String word, boolean[][] is_pass,int x,int y) {
	if(word.equals("")) return true;
	
	boolean flag = false;
	int len = matrix.length;
	int len1 = matrix[0].length;
	char first = word.charAt(0);
	
	if(x < len-1) {
		boolean[][] bs = copy(is_pass);
		if(!is_pass[x+1][y]) {
			if(first == matrix[x+1][y]) {
				bs[x+1][y] = true;
				flag = func(matrix,word.substring(1),bs,x+1,y);
			}
		}			
	}
	if(y < len1-1) {
		boolean[][] bs = copy(is_pass);
		if(!is_pass[x][y+1] && !flag) {
			if(first == matrix[x][y+1]) {
				bs[x][y+1] = true;
				flag = func(matrix,word.substring(1),bs,x,y+1);
			}
		}
	}
	if(x > 0) {
		boolean[][] bs = copy(is_pass);
		if(!is_pass[x-1][y] && !flag) {
			if(first == matrix[x-1][y]) {
				bs[x-1][y] = true;
				flag = func(matrix,word.substring(1),bs,x-1,y);
			}
		}
	}
	if(y > 0) {
		boolean[][] bs = copy(is_pass);
		if(!is_pass[x][y-1] && !flag) {
			if(first == matrix[x][y-1]) {
				bs[x][y-1] = true;
				flag = func(matrix,word.substring(1),bs,x,y-1);
			}
		}
	}
	
	return flag;
}

public boolean[][] copy(boolean[][] is_pass){
	int len = is_pass.length;
	int len1 = is_pass[0].length;
	boolean[][] arr = new boolean[len][len1];
	for(int i = 0;i < len;i++) {
		for(int j = 0;j < len1;j++) {
			arr[i][j] = is_pass[i][j];
		}
	}
	
	return arr;
}

public void clear(boolean[][] is_pass) {
	for(int i = 0;i < is_pass.length;i++) {
		for(int j = 0;j < is_pass[i].length;j++) {
			is_pass[i][j] = false;
		}
	}
}

}