解法：

算法思路：

我们需要假设每个位置的元素作为第⼀个字⺟，然后向相邻的四个⽅向进⾏递归，并且不能出现重复使⽤同⼀个位置的元素。通过深度优先搜索的⽅式，不断地枚举相邻元素作为下⼀个字⺟出现的可能性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。

递归函数设计：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;    以上就是本篇文章【递归、搜索与回溯算法：综合练习】的全部内容了，欢迎阅览 ！ 文章地址：http://w.yusign.com/quote/2830.html 
     行业      资讯      企业新闻      行情      企业黄页      同类资讯      网站地图      返回首页 述古往 http://w.yusign.com/mobile/ , 查看更多