矩阵中的路径

解答：
 1 public class Solution {
 2 
 3     public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
 4         if(matrix.length <= 0 || rows < 0 || cols < 0 || str.length <= 0) {
 5             return false;
 6         }
 7         
 8         boolean visited[] = new boolean[rows * cols];
 9         int [] index = {0};
10         for(int i = 0;i < rows;i ++) {
11             for(int j = 0;j < cols;j ++) {
12                 if(isPath(matrix, rows, cols, i, j, str, visited, index)) {
13                     return true;
14                 }
15             }
16         }
17         return false;
18     }
19     
20     public static boolean isPath(char[] matrix, int rows, int cols, int row, int col, char[] str, boolean visited[], int [] index) {
21         if(index[0] == str.length) {
22             return true;
23         }
24         
25         boolean flag = false; 
26         //当前点折算到原数组的位置是：row * cols + col
27         if(row >= 0 && row < rows && col >= 0 && col < cols 
28            && !visited[row * cols + col] && matrix[row * cols + col] == str[index[0]]) {
29             index[0] ++;    //指针右移
30             visited[row * cols + col] = true;
31             
32             //第一个点是合法的起点之后开始回溯:上下左右进行搜索
33             flag = isPath(matrix, rows, cols, row - 1, col, str, visited, index) || 
34                    isPath(matrix, rows, cols, row + 1, col, str, visited, index) ||
35                    isPath(matrix, rows, cols, row, col - 1, str, visited, index) ||
36                    isPath(matrix, rows, cols, row, col + 1, str, visited, index);
37 
38             if(!flag) {     //恢复现场
39                 index[0] --;
40                 visited[row * cols + col] = false;
41             }
42         }
43         
44         return flag;
45     }
46     
47     public static void main(String[] args) {
48         String str = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";
49         char[] matrix = str.toCharArray();
50         String str2 = "SGGFIECVAASABCEEJIGOEM";
51         char[] c = str2.toCharArray();
52         System.out.println(hasPath(matrix, 5, 8, c));
53     }
54 
55 }