矩阵中的路径-Java实现

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

讲讲为什么用DFS，而不能用BFS （个人看法，有误请批！）
这道题首先看出是DFS（深搜）问题，（为何是DFS，DFS就是用来不停探寻下一步，直至能否到达目的点，而另一种是BFS（广搜），BFS是用来找到源点到终点的最短路径。如果用BFS求解这道题，嗯？确定能用吗?BFS是以源点向四周扩散，以最短的扩散次数找到源点，听起来好像可以，我们可以一次次扩散找到路径中的每一个点，但是一般的BFS扩散一次，会把走过的结点标志为不可以走，那么假如第一个结点A四周扩散一次，四周走过，恰巧右方是第二个结点B，下方是最后一个结点E，那么以B怎么扩散都不能访问到E，因为E被走过，B怎么走都走不到E，所以个人觉得BFS不能用来解决这道题，只能用DFS一条路走到黑的方式来解决）

这道题就是以矩阵中的每一个点作为为起点去执行一次DFS。而DFS的执行过程就是：

1. 每次执行DFS先判断走过的路径是不是等于要求的路径，是就返回结果true，不是就继续找。
2. 先判断当前点是否可走，不是，则返回上一层；是就顺时针探寻下一个方位的结点（上、右、下、左），以下一个方位结点进行DFS，如果方位都探完了还找不到路径，那么当前节点不可能是路径结点之一，只能返回上一层。

Java代码实现

public class Solution {
    private boolean visited[] = null;//标志每个位置是否走过，true走过，false没走过

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null || str == null || str.length > matrix.length || rows * cols != matrix.length)
            //进行非法性判断
            return false;
        //初始化visited数组
        visited = new boolean[rows * cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //以每个结点作为起始节点去dfs
                if (dfs(matrix, i, j, rows, cols, str, 0))
                    return true;
            }
        }
        //没有找到
        return false;
    }

    /**
     * @param matrix 地图
     * @param x      起点x
     * @param y      起点y
     * @param rows   行数
     * @param cols   列数
     * @param str    所求路径
     * @param len    当前已经找到路径的长度
     * @return
     */
    private boolean dfs(char[] matrix, int x, int y, int rows, int cols, char[] str, int len) {
        if (len >= str.length) {
            //找到要求的路径
            return true;
        } else {
            //路径长度小于要求的长度，还得继续寻找
            if (x >= 0 && x <= rows - 1 && y >= 0 && y <= cols - 1 && visited[x * cols + y] == false && matrix[x * cols + y] == str[len]) {
                //当前结点是路径节点之一
                visited[x * cols + y] = true;//把当前结点的标志位设为true，证明走过了
                //寻找下一方位
                int dict = 0;
                int x1 = 0, y1 = 0;
                while (dict <= 3) {
                    switch (dict) {
                        case 0: x1 = x - 1; y1 = y; break;
                        case 1: x1 = x ; y1 = y + 1; break;
                        case 2: x1 = x + 1; y1 = y; break;
                        case 3: x1 = x ; y1 = y - 1; break;
                    }
                    if(dfs(matrix, x1, y1, rows, cols, str, len + 1))//判断下一个方位能否找到路径
                        return true; //能，直接返回
                    dict ++;//不能，找下一方位
                }
                //不能从当前结点找不到路径，那就回溯，把当前结点标志位设为false
                visited[x * cols + y] = false;
                return false;//返回失败
            } else{
                //当前结点不是要找的路径，直接回溯
                return false;
            }
        }
    }
}