剑指 Offer 12. 矩阵中的路径
创始人
2024-05-26 17:42:00
0

简单说两句

CSDN个人主页:后端小知识

🔎GZH后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

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

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

考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!
题目传送门: 剑指 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>& board, string word) {int m = board.size(), n = board[0].size();vector> visited(m, vector(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>& board, vector>& visited, string word, int i, int j, int k) {// 如果已经找到了单词的最后一个字符就返回trueif (k == word.size()) return true;// 如果当前位置越界、已经被访问过、或者当前位置的字符与单词中下一个要搜索的字符不匹配,就返回falseif (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;// 从当前位置的上、下、左、右四个方向递归地搜索下一个字符,如果在这些方向中任意一个方向找到符合条件的单词,就返回trueif (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个人主页:后端小知识

🔎GZH后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

相关内容

热门资讯

安卓系统相册软件下载,下载与使... 手机里的相册是不是已经满满当当,想要给它们找个新家?别急,今天就来给你安利几款超好用的安卓系统相册软...
安卓9系统优化软件,解锁流畅体... 你有没有发现,自从你的安卓手机升级到了安卓9系统,运行速度好像变得更快了?是不是觉得手机变得更加流畅...
各厂商安卓系统对比,性能、特色... 你有没有发现,现在手机市场上安卓系统的竞争可是相当激烈呢!各大厂商纷纷推出自己的特色系统,让人眼花缭...
车机进入安卓系统,智能驾驶体验... 你有没有发现,最近你的车机系统好像变得不一样了?没错,车机系统正在悄悄地进入安卓的大家庭!这可不是什...
安卓系统自带壁纸高清,自带高清... 亲爱的手机控们,你是否曾为安卓系统自带的那些高清壁纸而驻足欣赏?那些色彩斑斓、风格迥异的画面,是不是...
安卓机换成钟表系统,探索智能穿... 你有没有想过,你的安卓手机其实也可以换上钟表系统呢?是的,你没听错,就是那种优雅、简洁、充满艺术感的...
安卓lcs操作系统,轻量级、安... 你知道吗?在智能手机的世界里,有一个操作系统可是相当出名的,那就是安卓LCS操作系统。它就像一位魔法...
安卓系统微信包月,畅享无限制沟... 你知道吗?在咱们这个手机不离手的年代,微信可是咱们日常生活中不可或缺的好帮手。不过,你知道吗?安卓系...
我想换安卓系统,系统升级换新体... 亲爱的读者,你是否也有过这样的冲动?看着身边的朋友纷纷换上了安卓系统,心里痒痒的,也想尝试一下?没错...
用了苹果换安卓系统,系统更迭背... 你知道吗?最近我可是经历了一场大变身呢!是的,你没听错,我用苹果手机换成了安卓系统。这可不是一个小决...
手机刷机系统安卓,解锁手机潜能... 你有没有想过,你的手机是不是已经有点儿“老态龙钟”了呢?别急,别急,今天就来给你揭秘如何给手机来个焕...
安卓pe10系统,功能与特色深... 你有没有听说最近安卓PE10系统火得一塌糊涂?没错,就是那个让无数手机用户为之疯狂的系统。今天,我就...
安卓系统程序安装目录,安卓系统... 你有没有想过,当你手机里安装了一个又一个应用程序时,它们都藏在哪里呢?没错,就是那个神秘的安卓系统程...
ios系统能定位安卓系统吗,i... 你有没有想过,你的iPhone和安卓手机之间竟然能玩出这么一出“追踪大戏”?没错,我要说的就是那个让...
安卓系统时间放到桌面,桌面概览... 你有没有发现,手机上的时间有时候会偷偷跑得飞快,让你不知不觉就错过了重要的事情?别急,今天就来教你怎...
安卓系统怎么刷win,体验全新... 你有没有想过,把你的安卓手机变成一台Windows电脑呢?听起来是不是有点不可思议?但别急,今天我就...
安卓仿苹果系统设置,打造极致用... 你有没有发现,现在越来越多的安卓手机开始模仿苹果的操作系统了?没错,就是那个简洁又好用的设置界面!今...
emui 安卓系统对应关系,E... 你有没有发现,每次打开你的华为手机,那个界面看起来是不是特别顺眼?那是因为华为的EMUI系统,它就像...
永诺安卓系统相机,功能解析与使... 你有没有发现,手机拍照已经成为我们生活中不可或缺的一部分?而在这其中,永诺安卓系统的相机功能可是相当...
tinder安卓版系统错误,揭... 最近在使用Tinder安卓版的时候,你是不是也遇到了一些让人头疼的系统错误呢?别急,今天就来和你聊聊...