Above is the description of Nazca Lines from Wikipedia. Recently scientists found out that those lines form many crosses. Do those crosses have something to do with the Christian religion? Scientists are curious about this. But at first, they want to figure out how many crosses are there. So they took a huge picture of Nazca area from the satellite, and they need you to write a program to count the crosses in the picture.
To simplify the problem, we assume that the picture is an N*N matrix made up of 'o' and '#', and some '#' can form a cross. Here we call three or more consecutive '#' (horizontal or vertical) as a "segment".
The definition of a cross of width M is like this:
1) It's made up of a horizontal segment of length M and a vertical segment of length M.
2) The horizontal segment and the vertical segment overlap at their centers.
3) A cross must not have any adjacent '#'.
4) A cross's width is definitely odd and at least 3, so the above mentioned "centers" can't be ambiguous.
For example, there is a cross of width 3 in figure 1 and there are no cross in figure 2 ,3 and 4.
You may think you find a cross in the top 3 lines in figure 2.But it's not true because the cross you find has a adjacent '#' in the 4th line, so it can't be called a "cross". There is no cross in figure 3 and figure 4 because of the same reason.
In each test case:
The First line is a integer N, meaning that the picture is a N * N matrix ( 3<=N<=50) .
Next N line is the matrix.
The input end with N = 0
oo#o
o###
oo#o
ooo#
4
oo#o
o###
oo#o
oo#o
5
oo#oo
oo#oo
#####
oo#oo
oo##o
6
ooo#oo
ooo##o
o#####
ooo#oo
ooo#oo
oooooo
0
0
0
0
#include<stdio.h>
int n,sk,hk,s,h,stakH[1000],stakS[1000],right,lift,up,dow,zxloct;
char map[105][105];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; void DFS(int i,int j)
{
int e;
map[i][j]='o';
if(stakS[s]==j)
dow++;
for(e=0;e<4;e++)
if(e<2)
{
if(i+dir[e][0]>=0&&i+dir[e][0]<n&&j>=0&&j<n)
if(map[i+dir[e][0]][j]=='#')
{
sk++;
if(j!=stakS[s])
stakS[++s]=j;
DFS(i+dir[e][0],j+dir[e][1]);
}
}
else
{
if(i>=0&&i<n&&j+dir[e][1]>=0&&j+dir[e][1]<n)
if(map[i][j+dir[e][1]]=='#')
{
hk++;
if(e==2)
right++;
else
lift++;
if(i!=stakH[h])
stakH[++h]=i;
if(zxloct==-1)
{
zxloct=i; dow--;
} DFS(i,j+dir[e][1]);
}
}
if(zxloct==-1)
{
dow--;up++;
}
}
int main()
{
int i,j,k;
while(scanf("%d",&n)==1&&n)
{
k=0;getchar();
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
getchar();
}
stakH[0]=-1;
stakS[0]=-1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(map[i][j]=='#')
{
hk=s=h=0;
right=lift=0;
up=dow=0;
zxloct=-1;
sk=1;stakS[++s]=j;
DFS(i,j);
if(s==1&&h==1&&sk%2==1&&hk%2==0&&hk>0&&sk>1&&right==lift&&up==dow&&lift!=0&&up!=0)
k++;
} printf("%d\n",k);
}
}