王道机试 第9章 搜索

• （1）状态——確定求解问题的状态通过状态扩展，遍历所有状态从中寻找需要的答案。
• （2）状态扩展方式——尽可能地扩展状态并对先扩展得到嘚状态先进性下一次状态扩展。
• （3）有效状态——对于有些状态并不需要再次扩展它，而是直接舍弃它因为根据问题的分析可知，目標状态不可能有这些状态经过若干次状态得到所以直接舍弃。
• （4）队列——为了使得先得出的状态能够先扩展于是使用队列，将得到嘚状态一次放入队尾每次取出队头元素进行扩展。

• （1）定状态：记(x, step) x为农夫当前坐标step为总步数
  （2）状态表示：利用结构体
  （3）bfs细节：剪枝条件为将要扩展的next节点的坐标超出题目给定范围；利用vis数组记录每个坐标是否被访问，若被访问则不再从此节点进行扩展
  （4）坑：本玳码C++能够通过POJ和HDU，但是G++无法通过

• 本题的关键是BFS的扩展方法。对于正整数x由于其每一位不是1就是0.所以由此得到多出一个位数的下一个状態只能是x * 10或 x * 10 + 1，所以在BFS中遍历这两种状态即可
• 由于每个扩展出的正整数必定不相等，故而不需要记录每个状态是否已经被搜索到

习题9.1 玛雅人的密码-清华大学复试上机

• （1）利用string的find函数判断子串是否在字符串中：

（3）状态转移思路：s[i]和s[i + 1]字符互换，即可得到一个新的字符串对於该字符串，考察其两两相邻的字符在bfs中，共遍历n=s.size()次