http://acm.nyist.net/JudgeOnline/problem.php?pid=27
程序代码（一）：时间 8 内存 272
#include
#define N 102
#define M 102
int map[N][M] = {0};
void search(int i,int j)
//递归调用，将是 1 的 连续地方 全部 变为 0
//递归调用，将是 1 的 连续地方 全部 变为 0
{
if(map[i][j-1]) { map[i][j-1]=0;
search(i,j-1); }
search(i,j-1); }
if(map[i][j+1]) { map[i][j+1]=0;
search(i,j+1); }
search(i,j+1); }
if(map[i-1][j]) { map[i-1][j]=0;
search(i-1,j); }
search(i-1,j); }
if(map[i+1][j]) { map[i+1][j]=0;
search(i+1,j); }
search(i+1,j); }
}
int main()
{
int t,n,m;
int i,j,count;
scanf("%d",&t);
while(t--)
{
scanf("%d
%d",&n,&m);
%d",&n,&m);
count=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j])
{
count++;
map[i][j]=0;
search(i,j);
}
printf("%d\n",count);
}
return 0;
}
程序代码（二）：时间 4 内存
308
308
#include
#include
int
map[100][100],vis[100][100];
//这里定义两个数组同时搜索，时间少，但消耗内存大
map[100][100],vis[100][100];
//这里定义两个数组同时搜索，时间少，但消耗内存大
int
n,m;
n,m;
void
dfs(int i,int j)
dfs(int i,int j)
{
vis[i][j]=1;
if(map[i-1][j]&&!vis[i-1][j])
{
vis[i-1][j]=1;
dfs(i-1,j);
}
if(map[i+1][j]&&!vis[i+1][j])
{
vis[i+1][j]=1;
dfs(i+1,j);
}
if(map[i][j-1]&&!vis[i][j-1])
{
vis[i][j-1]=1;
dfs(i,j-1);
}
if(map[i][j+1]&&!vis[i][j+1])
{
vis[i][j+1]=1;
dfs(i,j+1);
}
}
int
main()
main()
{
int
i,j,sum,t;
i,j,sum,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
sum=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(!vis[i][j]&&map[i][j])
{
sum++;
dfs(i,j);
}
printf("%d\n",sum);
}
return 0;
}
程序代码（三）：时间 0 内存
248
248
#include
#include
char map[100][100],vis[100][100];//这里把数组定义成字符型数组，来存放整型数，减少了内现存和时间
int n,m;
void dfs(int i,int j)
{
vis[i][j]=1;
if(map[i-1][j]&&!vis[i-1][j])
{
vis[i-1][j]=1;
dfs(i-1,j);
}
if(map[i+1][j]&&!vis[i+1][j])
{
vis[i+1][j]=1;
dfs(i+1,j);
}
if(map[i][j-1]&&!vis[i][j-1])
{
vis[i][j-1]=1;
dfs(i,j-1);
}
if(map[i][j+1]&&!vis[i][j+1])
{
vis[i][j+1]=1;
dfs(i,j+1);
}
}
int main()
{
int i,j,sum,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
sum=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(!vis[i][j]&&map[i][j])
{
sum++;
dfs(i,j);
}
printf("%d\n",sum);
}
return 0;
}