作者：翟天保Steven
版權聲明：著作權歸作者所有，商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處

題目描述：

請設計一個函數(shù)，用來判斷在一個n乘m的矩陣中是否存在一條包含某長度為len的字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子，則該路徑不能再進入該格子。 例如A矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

數(shù)據(jù)范圍：0≤n,m≤20?,1≤len≤25?

示例：

輸入：

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

返回值：

true

解題思路：

本題是回溯法的經(jīng)典題目，也常用于解決迷宮問題。思路如下：

1. 用flag記錄當前點是否走過，結合矩陣數(shù)據(jù)和字符數(shù)據(jù)，運用dfs（深度優(yōu)先遍歷）進行路徑探索。
2. dfs中，若當前點出現(xiàn)下標越界、字符不匹配和已經(jīng)走過的情況，則終止當前路；若字符匹配上了，則認為當前點滿足要求，先暫時將flag設為true，并以該點為中心，繼續(xù)向上下左右四個方向探索新的點位；若四個方向有路可走，則依次遞進，直到有一條路徑和字符串完全對應；若四個方向均無路，則回退一步，并將當前點的flag設為false。

總的來說，題目運用了回溯、深度優(yōu)先遍歷和遞歸的思想。

測試代碼：

class Solution {
public:
    // 深度優(yōu)先遍歷
    bool dfs(vector<vector<char>>& matrix, int m, int n, int i, int j, string word, int k, vector<vector<bool>>& flag){
        // 下標越界、字符不匹配、已經(jīng)遍歷過，則false
        if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] != word[k] || flag[i][j])
            return false;
        // 刷新標識符
        flag[i][j]= true;
        // 字符串全部集齊，則true
        if(k == int(word.size() - 1))
            return true;
        // 上下左右四方向搜索，若有路通，則true    
        if(dfs(matrix, m, n, i - 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i + 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i, j - 1, word, k + 1, flag)
           || dfs(matrix, m, n, i, j +1 , word, k + 1, flag))
           return true;
        // 該點位無有效路徑，倒退一步，此點未使用，所以重置flag
        flag[i][j] = false;
        return false;
    }

    // 是否有目標路徑
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // 空數(shù)據(jù)判斷
        int m = int(matrix.size());
        int n = int(matrix[0].size());
        if(m == 0 || n == 0)
            return false;
        // flag二維容器存放標識符，判斷當前點是否走過
        vector<vector<bool>> flag(m,vector<bool>(n, false));
        // 遍歷
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(dfs(matrix, m, n, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
};

六一兒童節(jié)快樂！