#include <stdio.h> #include <string.h> #include <queue> using namespace std; int n; int vis[10000000]; int mode1,mode2; struct node { int step,status; }; void print(int x) { int tmp=x%2; if (!(x==0 || x==1)) print(x>>1); printf("%d",tmp); } int main() { int i,j,m,n; char str[100]; while (scanf("%d",&n)!=EOF) { memset(vis,0,sizeof(vis)); scanf("%s",str); scanf("%d",&m); // printf("!!1"); mode1=mode2=0; //printf("%s ",str); for (i=0;str[i]!=' ';i++) mode1=(mode1<<1)+(str[i]=='*'?1:0); for (i=strlen(str)-1;i>=0;i--) mode2=(mode2<<1)+(str[i]=='*'?1:0); // printf("mode1=%d ",mode1); node tmp; tmp.step=0; tmp.status=0; int end=(1<<m)-1; queue<node> q; q.push(tmp); vis[tmp.status]=1; int full=0; for (i=0;i<m;i++) full=(full<<1)+1; node tmp2; int flag=1; while (!q.empty()) { // printf("@@@ "); tmp=q.front(); q.pop(); tmp.status=tmp.status<<(n-1); for (i=0;i<(n+m);i++) { int nw=((tmp.status|(mode1<<i))>>(n-1))&(full); // printf("nw="); // print(nw); // printf(" %d ",i); if (vis[nw]==0) { vis[nw]=1; tmp2.status=nw; tmp2.step=tmp.step+1; if (tmp2.status==end) { printf("%d ",tmp2.step); flag=0; break; } q.push(tmp2); // printf("%d %d ",tmp2.status,tmp2.step); } } if (!flag) break; for (i=0;i<(n+m);i++) { int nw=((tmp.status|(mode2<<i))>>(n-1))&(full); // printf("nw=%d ",nw); // printf("nw2="); // print(nw); // printf(" %d ",i); if (vis[nw]==0) { vis[nw]=1; tmp2.status=nw; tmp2.step=tmp.step+1; if (tmp2.status==end) { printf("%d ",tmp2.step); flag=0; break; } q.push(tmp2); // printf("%d %d ",tmp2.status,tmp2.step); } } if (!flag) break; } if (flag==1) printf("-1 "); } return 0; }