矩阵中的路径

刚开始看到题觉得简单，不知道该怎么入手，看了别人题解，自己实现了一下；

思路：

• 1.每一个位置的字符都去判断；

• 2.拿到字符坐标后，首先判断该字符是否与目标字符串的首字符一致，若一致，判断该坐标的上下左右字符是否对应目标字符串的第二个字符，如果能对应上，将去判断对应上的这个字符的上下左右字符是否对应目标字符串的第三个字符...递归实现；

• 3.格子不能重复进入，需增加一个与matrix一致的boolean 数组；

  boolean[] isUsed = null;
  
  public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
  
    isUsed = new boolean[matrix.length];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 判断是否符合
            if (findPath(matrix, rows, cols, str, i, j, 0)) {
                return true;
            }
        }
    }
  
    return false;
  }
  
  private boolean findPath(char[] matrix, int rows, int cols, char[] str, int i, int j, int len) {
    // 判断传入坐标对应的值，是否与目标字符串len位置的字符一致，同时判断该位置是否已被使用
    if (matrix[i * cols + j] != str[len] || isUsed[i * cols + j]) return false;
    // 目标字符串最后一个字符也被匹配，返回true
    if (len == str.length - 1) return true;
    // 标记（i，j）已被占用
    isUsed[i * cols + j] = true;
    len++;
  
    if (i > 0 && findPath(matrix, rows, cols, str, i - 1, j, len)) return true;
    if (i < rows - 1 && findPath(matrix, rows, cols, str, i + 1, j, len)) return true;
    if (j > 0 && findPath(matrix, rows, cols, str, i, j - 1, len)) return true;
    if (j < cols - 1 && findPath(matrix, rows, cols, str, i, j + 1, len)) return true;
  
    // 如果（i，j）的上下左右都匹配不是目标字符串的下一个字符，将解除占用
    isUsed[i * cols + j] = false;
    return false;
  }