1.16 如何移动最少次数的三色旗

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为“Dutch Nation Flag”（他是荷兰人），而多数的作者则使用“Three-Color Flag”来称之。

假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，现在希望将之分类，并排列为蓝、白、红的顺序，要如何移动才能让次数最少？注意只能在绳子上进行这个动作，而且一次只能调换两个旗子。示意图如下：

分析与解答：

在一条绳子上移动，也就意味着在程序中只能使用一个阵列，不能使用辅助存储。问题的解法很简单，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移。如果要让移动次数最少的话，还需要一些技巧：

算法的主要思路为就是用三个下标b、w、r分别指向不同的旗子。其中b指向的从0开始连续排列的蓝色旗子的最后面的第一个非蓝色旗子，r指向的从最后一个序号开始连续排列的红色旗子的第一非红色旗子。例如：bbrwbbrr，那么b指向的就是序号为2的红色旗子，r指向的就是序号为倒数第三的蓝色旗子。

w作为可移动的指针来指引旗子的移动，当w指向的旗子是白色旗子的时候，w继续向前移动；当w指向的旗子是蓝色的时候，就需要把b所指的旗子和w所指的蓝色旗子交互；同理当w指的旗子是红色的时候就需要w所指的红色旗子和r所指的旗子交换。

实现代码如下：

程序的运行结果为