1. /**
    2.  * 面试题12：矩阵中的路径
    3.  * 题目描述：请设计一个函数，用来判断在一个矩阵钟是否存在一条包含某字符串所有字符的路径。
    4.  * 路径可以从矩阵的任意一格开始，每一步可以在矩阵的向左、右、上、下移动一个。
    5.  * 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子
    6.  */
    7. public class No12 {
    8.     public static void main(String[] args) {
    9.         //测试用例
    10.         //功能测试：
    11.         //边界值测试：
    12.         //特殊值测试：
    13.         char[] matrix = {'c','d','r','y','l','q'};
    14.         char[] str = {'c','q'};
    15.         System.out.println(hasPath(matrix,2,3,str));
    16.     }
    18.     public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
    19.         //标志数组位
    20.         int flag[] = new int[matrix.length];
    21.         //遍历矩阵，找到起点，并寻找路径
    22.         for (int i = 0; i < rows; i++) {
    23.             for (int j = 0; j < cols; j++) {
    24.                 if (helper(matrix, rows, cols, i, j, str, 0, flag))
    25.                     return true;
    26.             }
    27.         }
    28.         return false;
    29.     }
    31.     private static boolean helper(char[] matrix,int rows,int cols,int i,int
    32.             j,char[] str,int k,int[] flag) {
    33.         //初始位置的坐标值
    34.         int index = i * cols + j;
    35.         //递归终止条件，异常/越界/矩阵中的字符与字符串中的字符不相等/已经走过的位置
    36.         if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] !=
    37.                 str[k] || flag[index] == 1)
    38.             return false;
    39.         //已经与整个字符串匹配完毕
    40.         if(k == str.length - 1)
    41.             return true;
    42.         //设置标志位为1
    43.         flag[index] = 1;
    44.         //递归判断是否满足条件
    45.         if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)
    46.                 || helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)
    47.                 || helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)
    48.                 || helper(matrix, rows, cols, i, j + 1, str, k + 1, flag))
    49.         {
    50.             return true;
    51.         }
    52.         //回归到上一步的状态
    53.         flag[index] = 0;
    54.         return false;
    55.     }
    57. }