【Hot 100 刷题计划】 LeetCode 79. 单词搜索 | C++ 标准方向数组 DFS 与回溯

LeetCode 79. 单词搜索 题目描述题目级别中等给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1:输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]],word ABCCED输出true 破题思路网格 DFS 深度优先搜索这道题是经典的“迷宫寻宝”模型我们采用DFS深度优先搜索 回溯的算法框架。核心逻辑拆解寻找起点我们需要两层for循环遍历整个二维网格只要遇到和目标单词首字母相同的字符就把它作为起点启动 DFS。方向控制使用经典的算法竞赛套路——方向数组dx[4]和dy[4]。通过一个简单的for (int i 0; i 4; i)循环就能优雅地向上下左右四个方向进行位置的偏移试探。状态标记与回溯题目要求“同一个单元格内的字母不允许被重复使用”因此我们需要一个状态数组st来记录哪些格子当前正在路径中。向下探索前标记st[x][y] 1。如果后续这条路走不通碰壁退回来时必须把状态重置为st[x][y] 0以便其他路径重新经过这里。这就叫回溯。 C 代码实现 (保留原汁原味作者版)classSolution{public:intdx[4]{0,-1,0,1};intdy[4]{-1,0,1,0};intres0,m,n;intst[20][20];// 状态数组记录格子是否已被访问boolexist(vectorvectorcharboard,string word){mboard.size(),nboard[0].size();for(inti0;im;i)for(intj0;jn;j){// 找到与单词首字母匹配的起点if(board[i][j]word[0]){// 每次开启全新的寻找前清空访问状态memset(st,0,sizeofst);dfs(board,word,1,i,j);}}returnres;}voiddfs(vectorvectorcharboard,string word,intpos,intx,inty){// 递归终止条件成功拼出了目标单词if(posword.size()){res1;return;}// 向四个方向试探for(inti0;i4;i){intxxxdx[i],yyydy[i];// 越界检查 访问状态检查 字符匹配检查if(xx0xxmyy0yyn!st[xx][yy]board[xx][yy]word[pos]){st[x][y]1;// 标记当前起点为已访问dfs(board,word,pos1,xx,yy);// 向下一层深入探索st[x][y]0;// 回溯撤销标记尝试其他分支}}}};