剑指 Offer 12 矩阵中的路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 Offer 12 矩阵中的路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目： 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

剑指 Offer 12 矩阵中的路径
示例 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

思路：

题解：
根据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/
该题目可以从二维数组的任意位置进去开始找路径，因此写两个for循环来，如果有一个可以一直递归下去找到路径，返回true
在dfs中，如果超出i或者j的边界或者访问的当前元素不等于word中当前位置的元素，直接false
如果等于了，那么i和j都在范围并且当前元素也等于word当前元素，并且k等于word大小减1的话，
说明遍历到最后一个word元素了，并且也相等，那么直接true。
如果还没到最后一个，那么将当前board[i][j]的值保存到临时变量tmp中，
并将board[i][j]修改为一个可以标志该位置你已经访问的值，防止在上下左右访问的时候，
又访问到该元素，保存到临时变量tmp的目的是，为了等会回溯用。
紧接着，上下左右分别遍历看有没有和下一个word相等的，如果有不断递归，直到长度相等，
再后边加回溯，由于刚刚访问到的时候，修改了该处的值，为了不让重复访问，但是该路径没有找到可行的路
因此，递归返回到上一层去了，需要将该值回溯以下。文章来源地址https://www.toymoban.com/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;
}