Posted on 2013-06-14 20:30
happyac 阅读(1144)
评论(0) 编辑 收藏 引用 所属分类:
uva
总结
搜索问题，按深度优先的思路可以顺利通过。
分析
要求按字母序输出所有可能的解。思路如下：
- 假设最后的输出保存在 $order[0\dots n]$ 的数组中，第 $n$ 层迭代确定数组的第 $n$ 个元素，全部确定之后就输出，然后回溯。
- 进入第 $k$ 层迭代，假设当前元素为 $S = \{a,b,c,d,e\}$，当前规则为 $R = \{a<b, c<d\}$。有两个步骤：
- 选择第 $k$ 个元素。除当前出现在规则右边的元素之外，依字母选择。可选的元素是 $S^\prime = \{a,c\}$。
- 依次从 $S^\prime$ 中选取元素，例如 $a$，从 $S$ 中去掉已经选择的元素，然后去掉 $a$ 对应的规则，即 $R=\{c<d\}$，然后进行下一层迭代