65、矩阵中的路径 超级经典的题目

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

示例1

输入

"ABCESFCSADEE",3,4,"ABCCED"

返回值

true

示例2

输入

"ABCESFCSADEE",3,4,"ABCB"

返回值

false
1、DFS
//这道题是典型的深度优先遍历DFS的应用，原二维数组就像是一个迷宫，可以  //上下左右四个方向行走
//我们的二维数组board中每个数都作为起点和给定的字符串做匹配，我们需要
//一个和原二维数组board等大小的visited数组，是bool型的，用来记录当前位置
//是否被访问过。因为题目要求一个cell只能被访问一次。
//如果二维数组的当前字符和目标字符串str对应的字符相等，则对其上下左右四个邻字
//符串分别调用dfs的递归函数，只要有一个返回true，那么就表示找到对应的字符串 

bool dfs(vector<vector<char>> &board, char* str, int index, int x, int y,
    vector<vector<bool>>& visited) 

{
    if (index == strlen(str)) return true;//搜寻超过路径长度，符合条件，返回true，//此时已经超过最大程度了 strlen返回不带 ‘\0’的长度，此时str[k]已经越界了，所以这个判断一定要放在函数开头，如果放在if之后，str[k]会越界
    if ((x < 0) || (y < 0) || (x >= board.size()) || (y >= board[0].size()))
        return false;//访问越界，终止，返回false
    if (visited[x][y]) return false;//之前访问过，剪枝
    if (board[x][y] != str[index]) return false;//不相等，剪枝
    visited[x][y] = true;
    if (dfs(board, str, index + 1, x, y - 1, visited) || //上
        dfs(board, str, index + 1, x, y + 1, visited) ||     //下
        dfs(board, str, index + 1, x - 1, y, visited) ||     //左
        dfs(board, str, index + 1, x + 1, y, visited))      //右
        return true; //有符合要求的

    visited[x][y] = false;//记得此处改回false，以方便下一次遍历搜索。
    return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if (str == NULL || rows <= 0 || cols <= 0)
        return false;
    vector<vector<char>> board(rows, vector<char>(cols));
    for (int i = 0; i < rows; ++i) {//将matrix装入二维数组board中
        for (int j = 0; j < cols; ++j) {
            board[i][j] = matrix[i * cols + j];
        }
    }
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (dfs(board, str, 0, i, j, visited) == true)
                return true;//以矩阵board中的每个字符为起点进行广度优先搜索
            //找到一个符合条件的即返回true.
        }
    }
    return false;//遍历完都没