【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（深度优先搜索）+ 回溯的算法框架。

核心逻辑拆解：

1. 寻找起点：我们需要两层for循环遍历整个二维网格，只要遇到和目标单词首字母相同的字符，就把它作为起点启动 DFS。
2. 方向控制：使用经典的算法竞赛套路——方向数组dx[4]和dy[4]。通过一个简单的for (int i = 0; i < 4; i++)循环，就能优雅地向上下左右四个方向进行位置的偏移试探。
3. 状态标记与回溯：
   • 题目要求“同一个单元格内的字母不允许被重复使用”，因此我们需要一个状态数组st来记录哪些格子当前正在路径中。
   • 向下探索前，标记st[x][y] = 1。
   • 如果后续这条路走不通（碰壁），退回来时，必须把状态重置为st[x][y] = 0，以便其他路径重新经过这里。这就叫回溯。

💻 C++ 代码实现 (保留原汁原味作者版)

classSolution{public:intdx[4]={0,-1,0,1};intdy[4]={-1,0,1,0};intres=0,m,n;intst[20][20];// 状态数组，记录格子是否已被访问boolexist(vector<vector<char>>&board,string word){m=board.size(),n=board[0].size();for(inti=0;i<m;i++)for(intj=0;j<n;j++){// 找到与单词首字母匹配的起点if(board[i][j]==word[0]){// 每次开启全新的寻找前，清空访问状态memset(st,0,sizeofst);dfs(board,word,1,i,j);}}returnres;}voiddfs(vector<vector<char>>&board,string word,intpos,intx,inty){// 递归终止条件：成功拼出了目标单词if(pos==word.size()){res=1;return;}// 向四个方向试探for(inti=0;i<4;i++){intxx=x+dx[i],yy=y+dy[i];// 越界检查 && 访问状态检查 && 字符匹配检查if(xx>=0&&xx<m&&yy>=0&&yy<n&&!st[xx][yy]&&board[xx][yy]==word[pos]){st[x][y]=1;// 标记当前起点为已访问dfs(board,word,pos+1,xx,yy);// 向下一层深入探索st[x][y]=0;// 回溯：撤销标记，尝试其他分支}}}};