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

題目描述：

請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)n乘m的矩陣中是否存在一條包含某長(zhǎng)度為len的字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。 例如A矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。

數(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)典題目，也常用于解決迷宮問(wèn)題。思路如下：

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

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

測(cè)試代碼：

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){
        // 下標(biāo)越界、字符不匹配、已經(jīng)遍歷過(guò)，則false
        if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] != word[k] || flag[i][j])
            return false;
        // 刷新標(biāo)識(shí)符
        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;
        // 該點(diǎn)位無(wú)有效路徑，倒退一步，此點(diǎn)未使用，所以重置flag
        flag[i][j] = false;
        return false;
    }

    // 是否有目標(biāo)路徑
    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二維容器存放標(biāo)識(shí)符，判斷當(dāng)前點(diǎn)是否走過(guò)
        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é)快樂(lè)！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-514654.html

到了這里，關(guān)于劍指offer(C++)-JZ12：矩陣中的路徑(算法-回溯)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！