剑指Offer12——矩阵中的路径(回溯)

刺骨的言语ヽ痛彻心扉 2022-10-09 02:54 132阅读 0赞

# 回溯算法 #

## 问题描述：矩阵中的路径 ##

[剑指 Offer 12. 矩阵中的路径][Offer 12.]

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

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

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

![img][]

**示例 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

### 解题思路 ###

这道题用了两个方法：

*  DFS深度优先搜索：沿着一个方向走一直走到底，再回溯到上一个点朝另一个方向走一直走到底。  
    例如下图以A为起始点，假设只走一步，A->B已经走到底，回溯到A这个点换个方向A->S又走到底了
 *  剪枝：显然如果查找某个字符串光使用上面这个算法会有较多冗余计算，在DFS中如果不满足条件则直接返回。  
    例如下图，以A为起始点往上、下、左走会越界不满足条件也不满足匹配的字符串，直接剪枝不进行下一步计算。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]  
    理解了上面两个思想，我们以上图为例

1.  求出矩阵大小，先找到矩阵的入口也就是待匹配字符串的第一个字符
2.  找到后以该字符为原点沿着该字符的四个方向上、下、左、右分别执行DFS算法，找到下一个匹配字符
3.  找到匹配的字符后重复步骤2知道完全匹配字符串

bool exist(vector<vector<char>>& board, string word) {
        
    		//1.求出矩阵宽度和高度
    		rows = board.size();
    		cols = board[0].size();
    		//2.遍历整个矩阵，执行DFS深度优先搜索
    		for (int i = 0; i < rows; ++i)
    		{
        
    			for (int j = 0; j < cols; ++j)
    			{
        
    				//先找到入口待匹配的第一个字符执行dfs算法
    				if (dfs(board, word, i, j, 0))
    					return true;
    			}
    		}
    		//3.遍历完不满足条件返回false
    		return false;
    	}

算法的整体思路很简单，关键是步骤2DFS算法的设计，首先是**剪枝**

*  待匹配字符下一次查找方向越界，即x、y小于0或者x、y超出矩阵行和列
 *  矩阵board\[x\]\[y\]字符不等于待匹配字符word\[k\]
 *  矩阵board\[x\]\[y\]字符已经查找过即重复查找

前**两种情况直接写一个if判断即可**，第三种情况则每次找到这个匹配字符后就让board\[x\]\[y\]=’\\0’避免了重复查找

其次是当k等于待匹配字符大小时代表查找结束，直接返回false

/*
    	*  参数说明：
    	*   board：二维矩阵
    	*   word: 待匹配字符串word
    	*   x, y: 矩阵横纵坐标
    	*   k:     待匹配字符串下标，k == word.size()-1时代表找到了字符串word
    	*/
    	bool dfs(vector<vector<char>>& board, string word, int x, int y, int k)
    	{
        
    		//1.x,y越界 || board[x][y] != word[k]返回false
    		if (x < 0 || y < 0 || x >= rows || y >= cols || board[x][y] != word[k])
    			return false;
    		//2. k == word.size()-1时代表找到了字符串word
    		if (k == word.size() - 1)
    			return true;
    		//3.board[x][y] == word[k]的情况执行四个方向的dfs算法
    		board[x][y] = '\0';
    		int dx[4] = {
         0, -1, 0, 1 };
    		int dy[4] = {
         -1, 0, 1, 0 };
    		for (int i = 0; i < 4; ++i)
    		{
        
    			int m = x + dx[i];
    			int n = y + dy[i];
    			if (dfs(board, word, m, n, k + 1))
    				return true;
    		}
    		//4.四个方向都不满足，恢复现场
    		board[x][y] = word[k];
    		return false;
    	}

### 整体代码 ###

class Solution {
        
    public:
    	/*
    	*  参数说明：
    	*   board：二维矩阵
    	*   word: 待匹配字符串word
    	*   x, y: 矩阵横纵坐标
    	*   k:     待匹配字符串下标，k == word.size()-1时代表找到了字符串word
    	*/
    	bool dfs(vector<vector<char>>& board, string word, int x, int y, int k)
    	{
        
    		//1.x,y越界 || board[x][y] != word[k]返回false
    		if (x < 0 || y < 0 || x >= rows || y >= cols || board[x][y] != word[k])
    			return false;
    		//2. k == word.size()-1时代表找到了字符串word
    		if (k == word.size() - 1)
    			return true;
    		//3.board[x][y] == word[k]的情况执行四个方向的dfs算法
    		board[x][y] = '\0';
    		int dx[4] = {
         0, -1, 0, 1 };
    		int dy[4] = {
         -1, 0, 1, 0 };
    		for (int i = 0; i < 4; ++i)
    		{
        
    			int m = x + dx[i];
    			int n = y + dy[i];
    			if (dfs(board, word, m, n, k + 1))
    				return true;
    		}
    		//4.四个方向都不满足，恢复现场
    		board[x][y] = word[k];
    		return false;
    	}
    
    	bool exist(vector<vector<char>>& board, string word) {
        
    		//1.求出矩阵宽度和高度
    		rows = board.size();
    		cols = board[0].size();
    		//2.遍历整个矩阵，执行DFS深度优先搜索
    		for (int i = 0; i < rows; ++i)
    		{
        
    			for (int j = 0; j < cols; ++j)
    			{
        
    				//先找到入口待匹配的第一个字符执行dfs算法
    				if (dfs(board, word, i, j, 0))
    					return true;
    			}
    		}
    		//3.遍历完不满足条件返回false
    		return false;
    	}
    private:
    	int rows;
    	int cols;
    };

[Offer 12.]: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
[img]: /images/20221005/7352d80bb4684098adf893f8dbc5712c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221005/96f9be2c9262449d8b6d0af7f7fa1cb1.png