矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）,结果应该返回true。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子，结果应该返回false。

解题思路

深度优先搜索：遍历矩阵中字符，先朝一个方向搜索，在搜索过程中，如果遇到这条路不可能和目标字符串匹配成功的情况，则应立即返回，并回溯到上一个节点，沿另一个方向搜索。此外，需要注意沿着一个方向搜索的过程中，已经访问过的节点需要做标记。C++实现如下：

class Solution {
public:
    bool dfs(vector<vector<char>>& board, int i, int j, string &word, int k){
       // 坐标越界或者当前坐标和字符串的当前元素不匹配时
        if(i>=board.size() || i<0 || j<0 || j>=board[0].size() || board[i][j] != word[k])
            return false;
        // board[i][j] = word[k]
        if(k==word.size()-1)
            return  true;
        char tmp = board[i][j];
       // 对当前路径下访问过的坐标做标记
        board[i][j]= '/';
       // 递归朝着下或上或右或左的方向比较下一个元素是否匹配
        bool res = dfs(board, i+1, j, word, k+1) || dfs(board, i-1, j, word, k+1) || dfs(board, i, j+1, word, k+1) || dfs(board, i, j-1, word, k+1)
       // 回溯时需要将被访问过的标记去掉
        board[i][j] = tmp;
        return res;

    }
    bool exist(vector<vector<char>>& board, string word) {
        // i  j 为节点坐标，k为字符串中字符下标
        for(int i=0; i<board.size(); i++){
            for(int j=0; j<board[0].size(); j++){
                if(dfs(board, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
};