#include<stdio.h>#include<algorithm>#include<string.h>#include <queue>using namespace std;struct node{ bool a[22];}tmp,tmp1;queue<node> qu;int b[][2]={{0,0},{-1,0},{-1,-1},{1,0},{1,1},{0,1},{0,-1}},d,l[22];bool visited[(1<<21)+5];int c[22][7];int main(){ int n,i,j,ans,cnt,k,x,y,ii,jj,f[7]; f[0]=0;f[1]=1;f[2]=3;f[3]=6;f[4]=10;f[5]=15;f[6]=21; char str[30],ch; for(i=1;i<=21;i++) { l[i]=0; x=0; while(f[x]<i)x++; y=i-x*(x-1)/2; for(k=0;k<7;k++) { ii=x+b[k][0];jj=y+b[k][1]; if(ii>=1&&ii<=6&&jj>=1&&jj<=ii) c[i][l[i]++]=ii*(ii-1)/2+jj; } } while(scanf("%d",&n)!=EOF) { while(!qu.empty())qu.pop(); for(i=1;i<=n;i++) { gets(str); for(j=1;j<=i;j++) { ch=getchar(); if(ch=='.') tmp.a[i*(i-1)/2+j]=0; else tmp.a[i*(i-1)/2+j]=1; } } memset(visited,false,sizeof(visited)); n=(n+1)*n/2; d=0; cnt=0; for(i=1;i<=n;i++) { d=d*2+tmp.a[i]; if(tmp.a[i]==0) cnt++; } ans=cnt; visited[d]=true; qu.push(tmp); while(!qu.empty()) { tmp=qu.front(); qu.pop(); for(i=1;i<=n;i++) { if(tmp.a[i]==0) { tmp1=tmp; for(j=0;j<l[i];j++) tmp1.a[c[i][j]]=1-tmp.a[c[i][j]]; d=0;cnt=0; for(j=1;j<=n;j++) { d=(d<<1)+tmp1.a[j]; if(tmp1.a[j]==0) cnt++; } if(visited[d]==false) { visited[d]=true; ans=max(ans,cnt); if(ans==n) goto A; qu.push(tmp1); } } } }A: printf("%dn",ans); } return 0;}
