矩阵中的路径

import java.util.*;
public class Solution {
    //用于标记某个位置是否已经在当前路径中
    static int[][] rec;
    static int rowN,colN;
    public boolean hasPath (String matrix, int rows, int cols, String str) {
        // write code here
        rowN = rows;
        colN = cols;
        rec = new int[rows][cols];
        for(int r = 0; r < rows; r ++){
            for(int c = 0; c < cols; c++){
                //找到一个开始位置

                //是否可以从任意一个位置开始遍历呢？即使当前位置的值不等于str.charAt(0)，只要不把这个位置加入到路径中即可，
                //这种思路是错误的，会造成无法标记当前位置，从而导致死循环
                if(matrix.charAt(r * colN + c) == str.charAt(0)){
                    boolean flag = helper(matrix,r,c,str);
                    if(flag){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static boolean helper(String matrix,int r,int c, String restStr){
        if(restStr.length() == 1){
            return matrix.charAt(r * colN + c) == restStr.charAt(0);
        }
        if(matrix.charAt(r * colN + c) != restStr.charAt(0)){
            return false;
        }
        //防止再次遍历到当前位置
        rec[r][c] = 1;
        if(r - 1 >= 0 && rec[r - 1][c] == 0){
            boolean up = helper(matrix,r - 1,c,restStr.substring(1));
            if(up){
                return true;
            }
        }
        if(r + 1 < rowN && rec[r + 1][c] == 0){
            boolean down = helper(matrix,r + 1,c,restStr.substring(1));
            if(down){
                return true;
            }
        }
        if(c - 1 >= 0 && rec[r][c - 1] == 0){
            boolean left = helper(matrix,r,c - 1,restStr.substring(1));
            if(left){
                return true;
            }
        }
        if(c + 1 < colN && rec[r][c + 1] == 0){
            boolean right = helper(matrix,r,c + 1,restStr.substring(1));
            if(right){
                return true;
            }
        }
        //当一条路径遍历完成之后，可以再次访问当前位置
        rec[r][c] = 0;
        return false;
    }
}

public boolean hasPath(String matrix, int rows, int cols, String str) {
        // write code here
        if (matrix == null || matrix.length() == 0) return false;
        if (str == null || str.length() == 0) return true;
        boolean[][] isUsed = new boolean[rows][cols];// 记录使用过的元素
        for (int i = 0; i < rows; i++) {// 每个位置元素都开始一次
            for (int j = 0; j < cols; j++) {
                if (helper(i, j, 0, matrix, str, isUsed)) return true;
            }
        }
        return false;
    }

    private boolean helper(int row, int col, int curIndex, String matrix, String str, boolean[][] isUsed) {
        // 检查范围、检查是否走过该点，检查是否已经str对应的字符串是否到头
        if (row < 0 || row >= isUsed.length || col < 0 || col >= isUsed[0].length || isUsed[row][col] || curIndex >= str.length())
            return false;
        if (str.charAt(curIndex) == matrix.charAt(row * isUsed[0].length + col)) {
            if (str.length() == curIndex + 1) return true;
            isUsed[row][col] = true;
            boolean result = helper(row - 1, col, curIndex + 1, matrix, str, isUsed);//上
            if (result) return true;// 找到之后就不同向其他方向找，直接退出递归
            result = helper(row + 1, col, curIndex + 1, matrix, str, isUsed);//下
            if (result) return true;
            result = helper(row, col - 1, curIndex + 1, matrix, str, isUsed);//左
            if (result) return true;
            result = helper(row, col + 1, curIndex + 1, matrix, str, isUsed);//右
            if (result) return true;
            isUsed[row][col] = false;// 回溯
        }
        return false;
    }