URAL 1181 Cutting a Painted Polygon【再帰＋分治】

タイトル:
http://acm.timus.ru/problem.aspx?space=1&num=1181
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=27048#problem/A
1181.Cutting a Painted Polygon
Time limit：1.0 second
Memory limit:64 MB
The re is a convex polygon with vertices painted in three colors：Red（R），Green（G）and Blue（B）It is known that all the colors are present and any two neighbor vertices have different colors.You are to find out whether it is possible to cut is polygon with noncsing dingdions soreventone green and one blue vertex.Point out a possible way of the cutting if the cutting is possible.
Input
The first line contains a number 
N of the polygon vertices（4≦ 
N ≤1000).The re are 
N smbors of the set{'R'、'G'、'B''n in the second line that specify aカラーフォーマットthe cores pondent vertex.
Output
The first line shound contain einther a number of drawn diagonals in case the required cutting is possible or the number 0 otherswise(cutting is impossible)In the first case the following line s shound contain a description of the drawn diagonals.The description of a diagonal Tars line and consists of diagonal vertices numbers.The numbers are separated with therepartable。
Sample
input
out put

7
RBGBRGB

4
1 3
3 7
5 7
5 3

転載は：cxb：http://blog.csdn.net/cxb569262726/article/details/7845369

/**************************************************
A	Accepted	144 KB	31 ms	Visual C++ 2010	3410 B
  ：      N (4 < N < 1000)      ,
              'R','G','B'.
                    N-3     ,
                    .
          :   0
        ：   N-3    

  ：  +  

  ：      
                  > 1   ：
                        ，          ，      ，           
            ，           ，        ，         。
************************************************/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

const int maxn = 1000+10;
char str[maxn];
int index[maxn];

int dfs(char a[])
{
    int r,g,b;
    r = g = b = 0;
    int len = strlen(a);
    for(int i = 0; i < len; i++)
    {
        if(a[i] == 'R') r++;
        else if(a[i] == 'G') g++;
        else if(a[i] == 'B') b++;
    } /**                  */
    if(r == 1)
    {
        for(int i = 0; i < len; i++)
        {
            if(a[i] == 'R')
            {/**       */
                for(int j = i+2; j <= (i == 0 ? len-2 : len-1); j++)
                {
                    printf("%d %d
",index[i], index[j]);
                }
                for(int j = i-2; j >= (i == (len-1) ? 1 : 0); j--)
                {
                    printf("%d %d
", index[i], index[j]);
                }
                return 1;
            }
        }
    }
    if(g == 1)
    {
        for(int i = 0; i < len; i++)
        {
            if(a[i] == 'G')
            {
                for(int j = i+2; j <= (i == 0 ? len-2 : len-1); j++)
                {
                    printf("%d %d
",index[i], index[j]);
                }
                for(int j = i-2; j >= (i == (len-1) ? 1 : 0); j--)
                {
                    printf("%d %d
", index[i], index[j]);
                }
                return 1;
            }
        }
    }
    if(b == 1)
    {
        for(int i = 0; i < len; i++)
        {
            if(a[i] == 'B')
            {
                for(int j = i+2; j <= (i == 0 ? len-2 : len-1); j++)
                {
                    printf("%d %d
",index[i], index[j]);
                }
                for(int j = i-2; j >= (i == (len-1) ? 1 : 0); j--)
                {
                    printf("%d %d
", index[i], index[j]);
                }
                return 1;
            }
        }
    }
    else
    {
        for(int i = 0; i < len-3; i++)
        {
            if(a[i] != a[i+1] && a[i+1] != a[i+2] && a[i] != a[i+2])
            {
                printf("%d %d
", index[i], index[i+2]);
                for(int j = i+1; j < len-1; j ++) /**    i+1 */
                {
                    a[j] = a[j+1]; index[j] = index[j+1];
                }
                a[len-1] = '\0'; /**  */
                break;
            }
        }
    }
    if(dfs(a)) return 1;
    return 0;

}
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        scanf("%s",&str);
        int len = strlen(str);
        if(str[0] == str[len-1]) /**   ,      */
        {
            printf("0
");
            continue;
        }

        int r, g, b;
        r = g = b = 0;
        for(int i = 0; i < n; i++)
        {
            if(str[i] == 'R') r++;
            else if(str[i] == 'G') g++;
            else if(str[i] == 'B') b++;
            index[i] = i+1; /**    */
        }
        if(r == 0 || g == 0 || b == 0) /**   ,      */
        {
            printf("0
"); continue;
        }
        for(int i = 0; i < n-1; i++) /**   ,       */
        {
            if(str[i] == str[i+1])
            {
                len = -1;
                printf("0
");
                break;
            }
        }

        if(len == -1) continue;

        printf("%d
", n-3);
        dfs(str);
    }
    return 0;
}