- /*
- 问题:一字符串中有两种颜色,比如Red、Green
- 初始一字符串,只包含红色和绿色两种字符,
- 可以对这一字符串中的任意字符图上红色或者绿色,
- 要求:所有的红色字符都要在绿色字符的左边,同时,涂色的次数最少!!!
- */
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #define N 50
- int minPaint(char *,int);
- int leftPaint(char *,int);
- int rightPaint(char *,int); //从右边扫面
- int main(void)
- {
- char str[N];
- printf("请输入一串符合条件的字符串用于染色处理\\n");
- gets(str);
- int len=strlen(str);
- printf("最少染色次数是 %d\\n",minPaint(str,len));
- system("pause");
- return 0;
- }
- int rightPaint(char *s,int l)//从右边扫面
- {
- int gr,gl,rr,rl;
- gr=gl=rr=rl=0;
- int i,j,k,f;
- for(i=l-1;i>=0;i--)
- {
- if(s[i]=='g')
- { gr++; }
- else
- { break;}
- }
- for(j=i;j>=0;j--)
- {
- if(s[j]=='r')
- { rr++; }
- else
- { break;}
- }
- for(k=j;k>=0;k--)
- {
- if(s[k]=='g')
- { gl++; }
- else
- { break;}
- }
- for(f=k;f>=0;f--)
- {
- if(s[f]=='r')
- { rl++;}
- else
- { break;}
- }
- ////////////处理边界情况
- if(gl==0&&rl==0)
- return 0;
- if(gr==0&&rl==0)
- return gl>rr ? rr : gl;
- //////////其他情况都归纳在一起!!!!
- else
- {
- int min;
- if(gl>=rr)////////从右边扫面,注意等号
- {
- for(int x=0;x<rr;x++)
- {s[i-x]='g';}
- min=rr;
- }
- else
- {
- for(int x=0;x<gl;x++)
- {s[j-x]='r';}
- min=gl;
- }
- return min+rightPaint(s,l);
- }
- }
- int leftPaint(char *s,int l)////////从左边扫描
- {
- int gr,gl,rr,rl;
- gr=gl=rr=rl=0;
- int i,j,k,f;
- for(i=0;i<l;i++)
- {
- if(s[i]=='r')
- { rl++; }
- else
- { break;}
- }
- for(j=i;j<l;j++)
- {
- if(s[j]=='g')
- { gl++; }
- else
- { break;}
- }
- for(k=j;k<l;k++)
- {
- if(s[k]=='r')
- { rr++; }
- else
- { break;}
- }
- for(f=k;f<l;f++)
- {
- if(s[f]=='g')
- { gr++;}
- else
- { break;}
- }
- ////////////处理边界情况
- if(gr==0&&rr==0)
- return 0;
- if(gr==0&&rl==0)
- return gl>rr ? rr : gl;
- else
- {
- int min;
- if(rr>=gl)////从左边扫描,注意大于等于
- {
- for(int x=0;x<gl;x++)
- {s[i+x]='r';}
- min=gl;
- }
- else
- {
- for(int x=0;x<rr;x++)
- {s[j+x]='g';}
- min=rr;
- }
- return min+leftPaint(s,l);
- }
- }
- int minPaint(char *s,int l)
- {
- int left,right;
- char ls[N],rs[N];
- strcpy(ls,s);
- strcpy(rs,s);
- right=rightPaint(rs,l);
- printf("rightPaint's result %s and %d\\n",rs,right);
- left=leftPaint(ls,l);
- printf("leftPaint's result %s and %d\\n",ls,left);
- return left>right ? right :left;
- }
- //该片段来自于http://www.codesnippet.cn/detail/111020136340.html
来源: http://www.codesnippet.cn/detail/111020136340.html