URAL 1181 Cutting a Painted Polygon（解题报告）
转载请注明出处：http://blog.csdn.net/cxb569262726/article/details/7845369
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1181
代码如下：
#include<iostream>#include<algorithm>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<queue>#include<math.h>#include<set>#include<vector>#define MAXN 15#define INF 1000using namespace std;int r,b,g,lena,b1[1005];int dfs(char a[]){int i,j,lena=strlen(a);r=b=g=0;for(i=0;i<lena;i++){if(a[i]=='R') r++;else if(a[i]=='B') b++;else if(a[i]=='G') g++;}if(r==1){for(i=0;i<lena;i++)if(a[i]=='R'){for(j=i-2;j>=(i==lena-1?1:0);j--)printf("%d %d\n",b1[i]+1,b1[j]+1);for(j=i+2;j<(i==0?lena-1:lena);j++)printf("%d %d\n",b1[i]+1,b1[j]+1);}return 1;}else if(b==1){for(i=0;i<lena;i++)if(a[i]=='B'){for(j=i-2;j>=(i==lena-1?1:0);j--)printf("%d %d\n",b1[i]+1,b1[j]+1);for(j=i+2;j<(i==0?lena-1:lena);j++)printf("%d %d\n",b1[i]+1,b1[j]+1);}return 1;}else if(g==1){for(i=0;i<lena;i++)if(a[i]=='G'){for(j=i-2;j>=(i==lena-1?1:0);j--)printf("%d %d\n",b1[i]+1,b1[j]+1);for(j=i+2;j<(i==0?lena-1:lena);j++)printf("%d %d\n",b1[i]+1,b1[j]+1);}return 1;}else {for(i=0;i<lena-3;i++)if(a[i]!=a[i+1] && a[i]!=a[i+2] && a[i+1]!=a[i+2]){printf("%d %d\n",b1[i]+1,b1[i+2]+1);for(j=i+1;j<lena-1;j++){a[j]=a[j+1];b1[j]=b1[j+1];}a[lena-1]='\0';break;}}if(dfs(a)) return 1;return 0;}int main(){int i,j,n,m,t,c;char a[1005];while(~scanf("%d",&n)){r=b=g=0;scanf("%s",a);int len=strlen(a);if(a[0]==a[len-1]) {printf("0\n"); continue;}for(i=0;i<len-1;i++){if(a[i]==a[i+1]){printf("0\n"); len=-1;break;}}if(len==-1) continue;for(i=0;i<len;i++){if(a[i]=='R') r++;else if(a[i]=='B') b++;else if(a[i]=='G') g++;}if(r==0 || b==0 || g==0){printf("0\n"); continue;}printf("%d\n",n-3);for(i=0;i<n;i++) b1[i]=i;dfs(a);}return 0;}