Trim the Nails
Time Limit: 2 Seconds Memory Limit: 65536 KB
Robert is clipping his fingernails. But the nail clipper is old and the edge of the nail clipper is potholed.
The nail clipper's edge is N millimeters wide. And we use N characters('.' or '*') to represent the potholed nail clipper. '.' represents 1 bad millimeter edge, and '*' represents 1 good millimeter edge.(eg. "*****" is a 5 millimeters nail clipper with the whole edge good. "***..." is a 6 millimeters nail clipper with half of its edge good and half of its edge bad.)
Notice Robert can turn over the clipper. Turning over a "**...*"-nail clipper will make a "*...**"-nail clipper.
One-millimeter good edge will cut down Robert's one-millimeter fingernail. But bad one will not. It will keep the one-millimeter unclipped.
Robert's fingernail is M millimeters wide. How many times at least should Robert cut his fingernail?
Input
There will be multiple test cases(about 15). Please process to the end of input.
First line contains one integer N.(1≤N≤10)
Second line contains N characters only consists of '.' and '*'.
Third line contains one integer M.(1≤M≤20)
Output
One line for each case containing only one integer which is the least number of cuts. If Robert cannot clipper his fingernail then output -1.
Sample Input
8
****..**
4
6
*..***
7
Sample Output
1
2
Hint
We use '-' to present the fingernail.
For sample 1:
fingernail: ----
nail clipper: ****..**
Requires one cut.
For sample 2:
fingernail: -------
nail clipper: *..***
nail clipper turned over: ***..*
Requires two cuts.
題意：一把剪刀 有豁口 .表示豁口 *表示能用的地方 用剪刀剪指甲 指甲是平的 問最少需要多少次把所有的指甲剪掉
輸入n表示剪刀長度 輸入n個字符 輸入m表示指甲長度
比賽的時候只瞟了一眼 也沒仔細思考 就直接搞別的出題率高的題目去了 浪費了白花花的積分啊 主要原因還是自己速度太慢
要自信 要速度做題 遇到題目有了想法 不要畏手畏腳 要敢於拍出來 不行就果斷放棄 給別的題目騰出時間
另外做題中出現了好幾個細節錯誤 這些錯誤本應該在拍代碼中避免的 但是自己總是不夠嚴謹細心 以後要特意去加強下
還要加強代碼能力 越來越發現代碼能力的重要性了
[cpp]
#include<stdio.h>
#include<string.h>
int a[100];
int n,m,min,left,right;
void DFS(int b[],int s,int flag,int step)
{
int i,j,c[100];
if(step>=min) return;
if(flag)
{
for(i=1;i<=25;i++)
c[i]=b[i];
for(i=s,j=left;i<=m&&j<=n;i++,j++)
if(c[i]==0)
c[i]=a[j];
for(i=s;i<=m;i++)
if(c[i]==0)
{
s=i;break;
}
if(i==m+1)
{
if(step<min) min=step;
return ;
}
DFS(c,s,1,step+1);
DFS(c,s,0,step+1);
}
else
{
for(i=1;i<=25;i++)
c[i]=b[i];
for(i=s,j=right;i<=m&&j>0;i++,j--)
if(c[i]==0)
c[i]=a[j];
for(i=s;i<=m;i++)
if(c[i]==0)
{
s=i;break;
}
if(i==m+1)
{
if(step<min) min=step;
return ;
}
DFS(c,s,0,step+1);
DFS(c,s,1,step+1);
}
}
int main()
{
int i,b[100];
char ch;
while(scanf("%d",&n)!=EOF)
{
getchar();//這裡要有getchar 否則會影響下面的字符輸入
for(i=1;i<=n;i++)
{
scanf("%c",&ch);
if(ch=='*') a[i]=1;
else a[i]=0;
}
left=0;
for(i=1;i<=n;i++)
if(a[i]==1)
{
left=i;
break;
}
for(i=n;i>0;i--)
if(a[i]==1)
{
right=i;
break;
}
// for(i=1;i<=n;i++) printf("%d",a[i]);
scanf("%d",&m);
// printf("m=%d\n",m);
if(n==0) {printf("0\n");continue;}
if(left==0) {printf("-1\n");continue;}
memset(b,0,sizeof(b));
min=999999999;
DFS(b,1,1,1);
DFS(b,1,0,1);
printf("%d\n",min);
}
return 0;
}
