三色旗问题

0x55AA

1 问题由来
    三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。
    假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

2 解决思路：
    三种颜色的旗子，白色居中，蓝色开头，红色结尾，如果想要移动的次数最少，那么需要做的就是红色的往后面移动，蓝色的往前面移动，中间的白色尽量不动。
    算法的流程就是用三个信标b，w，r分别指向不同的旗子。其中b指向的从0开始连续排列的Blue旗子的最后面的第一个非Blue旗子，r指向的从最后一个序号开始连续排列的Red旗子的第一非Red旗子。例如：bbrwbbrr，那么b指向的就是序号为2的r，r指向的就是序号为倒数第三的b。w在这里里面起到的作用就是一个可以移动的指针。
    当w指向的旗子是White旗子的时候，w继续向前移动；当w指向的旗子是Blue的时候，就需要把b所指的旗子和w所指的Blue旗子交互；同理当w指的旗子是Red的时候就需要w所指的Red旗子和r所指的旗子交换。
    下图是起始时三个信标所指向的位置。

3 程序实现

1. #include <string>
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. int dutchFlag(string& str);
   
6. void swap(string& str,int x,int y);
   
7. 
   
8. void main()
   
9. {
   
10.         cout<<"Please input the dutch flags"<<endl;
    
11.         string str;
    
12.         cin>>str;
    
13.         int nTimes = dutchFlag(str);
    
14.         cout<<str<<endl;
    
15. 
    
16. }
    
17. int dutchFlag(string& str)
    
18. {
    
19.         int nLength = str.length();
    
20.         int fBlue = 0;
    
21.         int fWhite = 0;
    
22.         int fRed = nLength-1;
    
23.         int nCnt = 0;
    
24.         while( fWhite <= fRed )
    
25.         {
    
26.                 if(str[fWhite] == 'w')
    
27.                         fWhite++;
    
28.                 else if(str[fWhite] == 'b')
    
29.                 {
    
30.                         if( fWhite != fBlue )
    
31.                                 swap(str,fWhite,fBlue);
    
32.                         fWhite++;
    
33.                         fBlue++;
    
34.                         nCnt++;
    
35. 
    
36.                 }
    
37.                 else
    
38.                 {
    
39.                         // use fWhite < fRed to avoid 'wr':w point to r,and r point to r,then swap and error
    
40.                         while(str[fRed] == 'r' && fWhite < fRed)
    
41.                                 fRed--;
    
42.                         if( fWhite != fRed )
    
43.                                 swap(str,fWhite,fRed);
    
44.                         fRed--;
    
45.                         nCnt++;
    
46.                 }
    
47.         }
    
48.         return nCnt;
    
49. }
    
50. 
    
51. void swap(string &str,int x,int y)
    
52. {
    
53.         char tmp;
    
54.         tmp = str[x];
    
55.         str[x] = str[y];
    
56.         str[y] = tmp;
    
57.         cout<<x<<" swaps with "<<y<<endl;
    
58. }

复制代码

4 细节问题
4.1 当w和b所指向的位置一样的时候，如果不加限定条件 fWhite != fBlue的话，那么就会造自身的交换；同理当w和r同时指向最后的位置的时候，如果不加限定条件判断两者是否相等，那么也会造成自身与自身交换。
4.2

1. while(str[fRed] == 'r' && fWhite < fRed)

复制代码

   这个主要是为了防止例如wr的情况，这种情况下w指向r，r开始也指向r，w和r所指向的位置相同，然后r--，再然后w和r交换变成了rw，就这样导致了错误的发生。
加上限制条件 fWhite < fRed，那么此时r就不会再向前移动，因此就不会发生交换，从而避免了错误的发生。