这题陷阱很多....很多种不合法的贪食蛇...要仔细排除每种情况..
#include<stdio.h>
#include<string.h>
struct P
{
int i, j;
};
int n, m;
bool graph[201][201];
bool v[201][201];
int cnt;
bool is;
P head, tail;
bool ishead(int i, int j)
{
int c=0;
if(i-1>=0 && graph[i-1][j]==1)
c++;
if(j-1>=0 && graph[i][j-1]==1)
c++;
if(i+1<n && graph[i+1][j]==1)
c++;
if(j+1<m && graph[i][j+1]==1)
c++;
if(c==1 || c==0)
return 1;
else
return 0;
}
void DFS(int i, int j)
{
int c=0;
v[i][j]=1;
if(i-1>=0 && graph[i-1][j]==1)
c++;
if(j-1>=0 && graph[i][j-1]==1)
c++;
if(i+1<n && graph[i+1][j]==1)
c++;
if(j+1<m && graph[i][j+1]==1)
c++;
if(c>2)
is=0;
int cc=0;
if(i-1>=0 && graph[i-1][j]==1 && !v[i-1][j])
{
DFS(i-1,j);
cc++;
}
if(j-1>=0 && graph[i][j-1]==1 && !v[i][j-1])
{
DFS(i,j-1);
cc++;
}
if(i+1<n && graph[i+1][j]==1 && !v[i+1][j])
{
DFS(i+1,j);
cc++;
}
if(j+1<m && graph[i][j+1]==1 && !v[i][j+1])
{
DFS(i,j+1);
cc++;
}
if(cc==0)tail.i=i,tail.j=j;
}
bool b(int i, int j)
{
int c=0;
if(i-1<0)c++;
if(j-1<0)c++;
if(i+1==n)c++;
if(j+1==m)c++;
if(i-1>=0 && graph[i-1][j]==0)
c++;
if(j-1>=0 && graph[i][j-1]==0)
c++;
if(i+1<n && graph[i+1][j]==0)
c++;
if(j+1<m && graph[i][j+1]==0)
c++;
if(c==3)
return 1;
else
return 0;
}
bool bord(P p)
{
int i=p.i, j=p.j;
int c=0;
if(i-1>=0 && graph[i-1][j]==0 && b(i-1,j))
return 1;
else
if(j-1>=0 && graph[i][j-1]==0 && b(i,j-1))
return 1;
else
if(i+1<n && graph[i+1][j]==0 && b(i+1,j))
return 1;
else
if(j+1<m && graph[i][j+1]==0 && b(i,j+1))
return 1;
else
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(n==0 && m==0)break;
cnt=0;
memset(v,0,sizeof(v));
int i, j;
char c;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
{
scanf("\n%c", &c);
if(c=='1')graph[i][j]=1;
else graph[i][j]=0;
}
for(i = 0; i < n; i++)
for(j = 0 ;j < m; j++)
if(graph[i][j] && !v[i][j] && ishead(i,j))
{
is=1;
head.i=i, head.j=j;
DFS(i, j);
if(is && !bord(head) && !bord(tail))
{
// printf("%d %d : %d %d \n",head.i,head.j,tail.i,tail.j);
cnt++;
}
}
printf("%d\n", cnt);
}
return 0;
}