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};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;// 回溯：撤销标记，尝试其他分支}}}};
