題目： 給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過(guò)相鄰的單元格內(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

思路：

題解：
根據(jù)b站思路講解，加上力扣c++代碼
https://www.bilibili.com/video/BV1qK4y1E7ST/?spm_id_from=333.337.search-card.all.click&vd_source=cc3333a27046bad449a2b6818cc4149c
https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
該題目可以從二維數(shù)組的任意位置進(jìn)去開始找路徑，因此寫兩個(gè)for循環(huán)來(lái)，如果有一個(gè)可以一直遞歸下去找到路徑，返回true
在dfs中，如果超出i或者j的邊界或者訪問(wèn)的當(dāng)前元素不等于word中當(dāng)前位置的元素，直接false
如果等于了，那么i和j都在范圍并且當(dāng)前元素也等于word當(dāng)前元素，并且k等于word大小減1的話，
說(shuō)明遍歷到最后一個(gè)word元素了，并且也相等，那么直接true。
如果還沒(méi)到最后一個(gè)，那么將當(dāng)前board[i][j]的值保存到臨時(shí)變量tmp中，
并將board[i][j]修改為一個(gè)可以標(biāo)志該位置你已經(jīng)訪問(wèn)的值，防止在上下左右訪問(wèn)的時(shí)候，
又訪問(wèn)到該元素，保存到臨時(shí)變量tmp的目的是，為了等會(huì)回溯用。
緊接著，上下左右分別遍歷看有沒(méi)有和下一個(gè)word相等的，如果有不斷遞歸，直到長(zhǎng)度相等，
再后邊加回溯，由于剛剛訪問(wèn)到的時(shí)候，修改了該處的值，為了不讓重復(fù)訪問(wèn)，但是該路徑?jīng)]有找到可行的路
因此，遞歸返回到上一層去了，需要將該值回溯以下。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-489235.html

class Solution {
public:

	int m;//行
	int n;//列
	bool exist(vector<vector<char>>& board,string& word) {
		m = board.size();
		n = board[0].size();


		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (dfs(board, word, i, j, 0)) {
					return true;
				}
			}
		}
		return false;
	}
	bool dfs(vector<vector<char>>& board, string& word,int i,int j,int k) {
		if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k])return false;
		if (k == word.size() - 1)return true;
		int tmp = board[i][j];
		board[i][j] = '#';
		bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
			dfs(board,word,i,j+1,k+1) || dfs(board,word,i,j-1,k+1);
		board[i][j] = tmp;
		return res;
	}
};

int main() {
	vector<vector<char>> board{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
	Solution ss;
	string word = "ABCCED";
	cout << ss.exist(board,word) << endl;
	return 0;
}

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