剑指 Offer 12. 矩阵中的路径

矫情吗；* 2024-04-20 07:23 73阅读 0赞

⭐**简单说两句**⭐

> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

Hello吖，各位小伙伴大家好呀，今天我采用了一种**特别的方式**?来写题解，大家可以猜一猜额（**答案放在文末**）

题目： 剑指 Offer 12. 矩阵中的路径  ，我们今天来看一个经典的回溯算法问题，可以使用**深度优先搜索（DFS）+回溯来解决**，这是选自**剑指Offer**上的一道题，好了，我们一起来看看题意吧：

考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接题目链接放下面！  
题目传送门： [剑指 Offer 12. 矩阵中的路径][Offer 12.]

![image-20230224001554170][]

`思路`:

1.  遍历二维字符网格board，寻找和单词word第一个字母相同的字符，即`board[i][j]==word[0]`。
2.  对于`board[i][j]`等于word第一个字母的情况，进行深度优先搜索，从当前字符`board[i][j]`出发，向上、下、左、右四个方向进行搜索。
3.  在每个方向上，判断下一个字符是否等于word中的下一个字符，如果相等，则继续递归搜索，否则返回上一层。
4.  如果搜索到word的最后一个字符，则说明存在这个单词，返回true；否则，返回false。

`我们来看看成功AC的代码吧：`

class Solution {
        
    public:
        bool exist(vector<vector<char>>& board, string word) {
        
            int m = board.size(), n = board[0].size();
            vector<vector<bool>> visited(m, vector<bool>(n, false)); // 初始化visited数组
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (board[i][j] == word[0]) {
         // 如果当前字符匹配到了单词中的第一个字符
                        if (dfs(board, visited, word, i, j, 0)) {
         // 进行深度优先搜索
                            return true; // 如果找到符合条件的单词，就返回true
                        }
                    }
                }
            }
            return false; // 如果遍历了整个矩阵都没有找到符合条件的单词，就返回false
        }
    
        bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int i, int j, int k) {
        
            // 如果已经找到了单词的最后一个字符就返回true
            if (k == word.size()) return true;
            // 如果当前位置越界、已经被访问过、或者当前位置的字符与单词中下一个要搜索的字符不匹配，就返回false
            if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) return false;
            // 标记当前位置已经访问过
            visited[i][j] = true;
            // 从当前位置的上、下、左、右四个方向递归地搜索下一个字符，如果在这些方向中任意一个方向找到符合条件的单词，就返回true
            if (dfs(board, visited, word, i + 1, j, k + 1) || dfs(board, visited, word, i - 1, j, k + 1) ||
            dfs(board, visited, word, i, j + 1, k + 1) || dfs(board, visited, word, i, j - 1, k + 1)) {
        
                return true;
            }
            // 如果在所有方向中都没有找到符合条件的单词，就回溯到上一个字符位置，并将其标记为未访问过
            visited[i][j] = false; 
            return false;
        }
    };

================

OKOK，题解完毕，这道题算是比较经典了，结合注释相信大家都看懂了吧，看懂了的掌声响起来?，若还有不懂的地方，也是可以录制视频来讲解的额（掌声响起来?）

可能有的小伙伴已经猜到了我前面说的**特别的方式**了哈，没错，就是ChatGPT（就不多介绍了哈，有兴趣的老板可以在评论区留言或者投投票，若人数多的话就专门出一篇文章来聊聊ChatGPT)?

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!???

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[Offer 12.]: https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/description/
[image-20230224001554170]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/bd2231400e1d40868f13b1e175da8b8f.png