1、題目描述

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

例如，在下面的 3×4 的矩陣中包含單詞 “ABCCED”（單詞中的字母已標(biāo)出）。

示例 1：
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
輸出：true
示例 2：
輸入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
輸出：false

2、VS2019上運(yùn)行

使用回溯的方法

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {
        // 檢查當(dāng)前坐標(biāo)的字母是否與目標(biāo)單詞中的對(duì)應(yīng)字母相等
        if (board[i][j] != s[k]) {
            return false;
        }
        // 如果已經(jīng)匹配到目標(biāo)單詞的最后一個(gè)字母，表示找到了路徑，返回true
        else if (k == s.length() - 1) {
            return true;
        }

        visited[i][j] = true; // 將當(dāng)前坐標(biāo)標(biāo)記為已訪問
        vector<pair<int, int>> directions{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 上、下、左、右四個(gè)方向

        bool result = false; // 用于記錄是否找到路徑

        // 依次遍歷四個(gè)方向
        for (const auto& dir : directions) {
            int newi = i + dir.first, newj = j + dir.second; // 計(jì)算新坐標(biāo)
            // 檢查新的坐標(biāo)是否在矩陣范圍內(nèi)且沒有被訪問過
            if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
                if (!visited[newi][newj]) {//用于檢查位置(newi, newj)是否已經(jīng)被訪問過
                    // 遞歸調(diào)用check函數(shù)進(jìn)行下一步的搜索
                    bool flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true; // 如果找到路徑，直接返回true
                        break;
                    }
                }
            }
        }

        visited[i][j] = false; // 撤銷對(duì)當(dāng)前坐標(biāo)的標(biāo)記
        return result;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size(); // 矩陣的行數(shù)和列數(shù)
        vector<vector<int>> visited(h, vector<int>(w)); // 記錄每個(gè)格子的訪問狀態(tài)

        // 遍歷矩陣的每個(gè)格子，對(duì)每個(gè)格子調(diào)用check函數(shù)
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                bool flag = check(board, visited, i, j, word, 0); // 調(diào)用check函數(shù)進(jìn)行搜索
                if (flag) {
                    return true; // 如果找到路徑，直接返回true
                }
            }
        }

        return false; // 遍歷結(jié)束后仍未找到路徑，返回false
    }
};

int main() {
    // 示例用法
    vector<vector<char>> board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };

    Solution s;
    string word = "ABCCED";

    if (s.exist(board, word)) {
        cout << "Word exists in the board." << endl;
    }
    else {
        cout << "Word does not exist in the board." << endl;
    }

    return 0;
}

Word exists in the board.

3、整體思路

整體的思路是使用深度優(yōu)先搜索（DFS）算法在矩陣中搜索是否存在與目標(biāo)單詞匹配的路徑。文章來源地址http://www.zghlxwxcb.cn/news/detail-634094.html

• 首先，定義一個(gè) check 函數(shù)來進(jìn)行遞歸的搜索。該函數(shù)接收當(dāng)前的坐標(biāo) (i, j)、目標(biāo)單詞 s、以及目前匹配的字符索引 k。函數(shù)的返回值是一個(gè)布爾值，表示是否找到了匹配的路徑。
• 在 check 函數(shù)中，首先進(jìn)行邊界條件的判斷。如果當(dāng)前索引 k 已經(jīng)匹配到目標(biāo)單詞的最后一個(gè)字符，說明已經(jīng)找到了匹配的路徑，返回 true。
• 接下來，檢查當(dāng)前坐標(biāo) (i, j) 處的字母是否與目標(biāo)單詞中的對(duì)應(yīng)字母相等。如果不相等，說明當(dāng)前路徑匹配失敗，返回 false。
• 檢查新坐標(biāo)是否在矩陣的范圍內(nèi)，并且該位置沒有被訪問過（即 visited[newi][newj] = false）。
  如果滿足上述條件，則遞歸調(diào)用 check 函數(shù)，在新坐標(biāo) (newi, newj) 上繼續(xù)匹配下一個(gè)字符，即 k + 1。
• 如果遞歸調(diào)用返回 true，表示在某個(gè)方向上找到了匹配的路徑，直接返回 true。
  如果所有方向的遞歸調(diào)用都沒有找到匹配的路徑，則撤銷對(duì)當(dāng)前坐標(biāo) (i, j) 的標(biāo)記，將 visited[i][j] 設(shè)置為 false，表示可以重新訪問該位置。
• 最后，如果所有方向都探索完畢，仍然沒有找到匹配的路徑，則返回 false，表示沒有找到路徑。
• 接下來可以調(diào)用 check 函數(shù)，從矩陣的每個(gè)位置出發(fā)，判斷是否存在與目標(biāo)單詞匹配的路徑。如果返回 true，則說明存在這樣的路徑；如果返回 false，則說明不存在。
• 這就是整體的思路，通過DFS算法搜索矩陣中的路徑，并利用遞歸和回溯的思想進(jìn)行搜索和撤銷標(biāo)記。

4、int h = board.size(), w = board[0].size();

• 這行代碼int h = board.size(), w = board[0].size();的作用是獲取二維字符向量board的行數(shù)h和列數(shù)w。
• 1.board.size()返回二維字符向量board的行數(shù)，即向量中包含的子向量個(gè)數(shù)。
  2.board[0].size()返回二維字符向量board中第一行子向量的列數(shù)，假設(shè)矩陣不為空。

5、vector<vector> visited(h, vector(w));

• 這行代碼vector<vector<int>> visited(h, vector<int>(w));創(chuàng)建了一個(gè)名為visited的二維整數(shù)向量，其大小與輸入矩陣board的行數(shù)和列數(shù)相同。
• 1.vector<int>(w)部分創(chuàng)建了一個(gè)大小為w的整數(shù)向量。
• 2.vector<vector<int>> visited(h, vector<int>(w));使用上述創(chuàng)建的子向量為每一行創(chuàng)建了一個(gè)整數(shù)向量，從而形成了一個(gè)大小為h行、w列的二維整數(shù)向量visited。
• 這樣的二維向量visited可以用于跟蹤和記錄在處理board矩陣時(shí)已經(jīng)訪問過的位置或標(biāo)記。

6、dir.first 和dir.second

• dir.first表示dir這個(gè)pair（鍵值對(duì)）中的第一個(gè)元素，即表示方向的行坐標(biāo)變化。在該上下左右的方向向量中，dir.first表示上下移動(dòng)的行坐標(biāo)的變化量。
• 例如，如果dir是(-1, 0)，那么dir.first就是-1，表示向上移動(dòng)1行。同理，如果dir是(1, 0)，那么dir.first就是1，表示向下移動(dòng)1行。
• 在搜索一個(gè)矩陣的周圍方向時(shí)，dir.first的值用于計(jì)算新的行坐標(biāo)。通過將當(dāng)前位置的行坐標(biāo)i與dir.first相加，可以得到新的行坐標(biāo)，用于在矩陣中檢查相鄰位置是否符合要求。

7、visited[i][j] = false;

• 這行代碼為撤銷對(duì)當(dāng)前坐標(biāo)(i, j)的訪問標(biāo)記，將其重新設(shè)置為false。
• 標(biāo)記的目的是為了跟蹤遍歷矩陣時(shí)已經(jīng)訪問過的位置，以避免重復(fù)訪問。在代碼中，visited向量用于標(biāo)記位置是否已經(jīng)被訪問過。
• 當(dāng)程序進(jìn)行完成對(duì)位置(i, j)的處理后，如果希望在后續(xù)的搜索或迭代中能夠重新訪問該位置，就需要撤銷對(duì)該位置的訪問標(biāo)記，將visited[i][j]重新設(shè)置為false。
• 撤銷對(duì)當(dāng)前坐標(biāo)的標(biāo)記允許在后續(xù)的遍歷或搜索過程中重新考慮訪問該位置，以發(fā)現(xiàn)其他可能的路徑或結(jié)果。如果不撤銷標(biāo)記的話，可能會(huì)導(dǎo)致某些位置被錯(cuò)誤地標(biāo)記為已訪問，從而錯(cuò)過了找到其他路徑或結(jié)果的機(jī)會(huì)。因此，需要在適當(dāng)?shù)臅r(shí)候撤銷對(duì)當(dāng)前坐標(biāo)的標(biāo)記。

8、for (const auto& dir : directions)

• for (const auto& dir : directions) 是一個(gè)范圍-based的循環(huán)語句，用于遍歷容器 directions 中的元素。
• 在這個(gè)語句中，dir 是一個(gè)臨時(shí)變量，它會(huì)依次取到 directions 中的每個(gè)元素值。關(guān)鍵字 auto 會(huì)自動(dòng)推斷 dir 的類型，使其與 directions 中的元素類型保持一致。const 修飾符表示 dir 是一個(gè)常量，即在循環(huán)體內(nèi)不能對(duì)它進(jìn)行修改。
• 通過這個(gè)循環(huán)語句，可以依次遍歷 directions 容器中的每個(gè)方向，執(zhí)行相應(yīng)的操作，如計(jì)算新坐標(biāo) (newi, newj)，進(jìn)行路徑匹配等。這樣可以依次嘗試不同的方向，以搜索矩陣中是否存在與目標(biāo)單詞匹配的路徑。

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