JZ65 矩阵中的路径

显然要用dfs。值得注意的点：

1. 共用一个boolean[][]来记录访问过的点，节约空间，遍历前标记，遍历后恢复。
2. 多次使用的代码单独写成函数，如validate， index。
3. 移动方向单独用一个二维矩阵记录然后用循环，比直接写四个if语句要快。

   public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        if(rows==0||cols==0) return str==null||str.length==0;
        this.matrix=matrix;
        this.str=str;
        visited=new boolean[rows][cols];
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                visited[i][j]=true;
                if(matrix[index(i,j)]==str[0]&&dfs(1, i, j))
                    return true;
                visited[i][j]=false;
            }
        }
        return false;
    }
    char[] matrix;
    char[] str;
    boolean[][] visited;
    int[][] moves=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int index(int i, int j){
        return i*visited[0].length+j;
    }
    boolean validate(int i, int j){
        return i>=0&&i<visited.length&&j>=0&&j<visited[0].length;
    }
    boolean dfs(int curr, int i, int j){
        if(curr==str.length) return true;
        for(int[] move:moves){
            int x=i+move[0], y=j+move[1];
            if(validate(x,y)&&!visited[x][y]&&matrix[index(x,y)]==str[curr]){
                visited[x][y]=true;
                if(dfs(curr+1, x, y)) return true;
                visited[x][y]=false;
            }            
        }
        return false;
    }
   }