解法：
算法思路：
我们需要假设每个位置的元素作为第⼀个字⺟，然后向相邻的四个⽅向进⾏递归，并且不能出现重复使⽤同⼀个位置的元素。通过深度优先搜索的⽅式，不断地枚举相邻元素作为下⼀个字⺟出现的可能性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。
递归函数设计：bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos)
参数：i（当前需要进⾏处理的元素横坐标），j（当前需要进⾏处理的元素横坐标），pos（当前已
经处理的元素个数），word（字符串）；
函数作⽤：判断当前坐标的元素作为字符串中下标 pos 的元素出现时，向四个⽅向传递，查找是否存在路径结果与字符串相同。
递归函数流程：
1.
遍历每个位置，标记当前位置并将当前位置的字⺟作为⾸字⺟进⾏递归，并且在回溯时撤回记。
2.
在每个递归的状态中，我们维护⼀个步数 pos，表⽰当前已经处理了⼏个字⺟。
◦
若当前 pos 的值与字符串⻓度相等，表⽰存在⼀种路径使得 word 成⽴，返回 true。
3.
对当前位置的上下左右四个相邻位置进⾏递归，若递归结果为 true，则返回 true。
4.
若相邻的四个位置的递归结果都为 false，则返回 false。
•
特别地，如果使⽤将当前遍历到的字符赋值为空格，并在回溯时恢复为原来的字⺟的⽅法，则在递归时不会重复遍历当前元素，可达到不使⽤标记数组的⽬的。
解法：
算法思路：
对于四个⽅向，我们可以定义两个一维数组 dx，dy
，⼤⼩为
4
，每⼀维存储四个⽅向的坐标偏移量 （详⻅代码）。题⽬要求到达⽬标位置时所有⽆障碍⽅格都存在路径中，我们可以定义⼀个变量记录 num 当前状态中剩余的未⾛过的⽆障碍⽅格个数，则当我们⾛到⽬标地点时只需要判断 num 是否为 0 即可。在移动时需要判断是否越界。
全局变量：
vector<vector<bool>> visited;
int m, n;
int ret,cou=0;
int m, n;
int ret,cou=0;
特别提示：本信息由相关用户自行提供，真实性未证实，仅供参考。请谨慎采用，风险自负。
0 条相关评论