矩阵中的路径

直接使用回溯，用双重for循环，以每一个点为起点，去向四面走，找到符合条件的路径。走过的点用数组进行标记。

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flag = new int[matrix.length];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(helper(matrix,rows,cols,i,j,flag,0,str))
                    return true;
            }
        }
        return false;
    }

    public boolean helper(char[] matrix, int rows, int cols, int i, int j, int[] flag, int len, char[] str){
        int index = cols*i+j;  // 计算得到当前点在matrix的位置
        if(i<0 || i>=rows || j<0 || j>=cols || matrix[index]!=str[len] || flag[index] == 1) 
            /*超出范围，这个点不是我们想要的，或者这个点已经走过了，就不能再走了，直接返回false*/
            return false;
        // 长度相等的时候，就证明找到了
        if(len == str.length-1)
            return true;
        flag[index] = 1;  // 标记为已经走过了
        /*找到任何一条路径就够了*/
        if(helper(matrix,rows,cols,i-1,j,flag,len+1,str) || helper(matrix,rows,cols,i,j-1,flag,len+1,str) ||
          helper(matrix,rows,cols,i+1,j,flag,len+1,str) || helper(matrix,rows,cols,i,j+1,flag,len+1,str))
            return true;
        flag[index] = 0;  //撤销已经走过的点

        return false;
    }


}