科技冬令營信息學 奧林匹克競賽樣題 八、草場普查
遞迴的DFS
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
int map[102][102];
void map2(int b,int a,int ans)
{
if(map[b-1][a]>0) { map[b-1][a]=ans;map2(b-1,a,ans); }
if(map[b][a-1]>0) { map[b][a-1]=ans; map2(b,a-1,ans); }
if(map[b][a+1]>0) { map[b][a+1]=ans; map2(b,a+1,ans); }
if(map[b+1][a]>0) { map[b+1][a]=ans; map2(b+1,a,ans); }
}
main()
{
int a,b,c,n,m,time=0;
while(scanf("%d %d",&n,&m)==2)
{
int grass[102][102],ans2[10000]={0},max=0;
for(a=0;a<102;a++)
for(b=0;b<102;b++)
map[a][b]=0;
int ans=0;
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
{
scanf("%d",&map[b][a]);
grass[b][a]=map[b][a];
}
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
if(map[b][a]>0)
{
ans--;
map[b][a]=ans;
map2(b,a,ans);
}
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
ans2[abs(map[b][a])]+=grass[b][a];
ans=abs(ans);
for(a=1;a<=ans;a++)
if(ans2[a]>max) max=ans2[a];
printf("%d\n%d\n",abs(ans),max);
}
return 0;
}
/**********************************************************/
優化輸入...優一下8Xms...
#include<stdio.h>
#include<stdlib.h>
int input()
{
char cha;
int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
int map[102][102];
void map2(int b,int a,int ans)
{
if(map[b-1][a]>0) { map[b-1][a]=ans;map2(b-1,a,ans); }
if(map[b][a-1]>0) { map[b][a-1]=ans; map2(b,a-1,ans); }
if(map[b][a+1]>0) { map[b][a+1]=ans; map2(b,a+1,ans); }
if(map[b+1][a]>0) { map[b+1][a]=ans; map2(b+1,a,ans); }
}
main()
{
int a,b,c,n,m,time=0;
while(scanf("%d %d",&n,&m)==2)
{
int grass[102][102],ans2[10000]={0},max=0;
for(a=0;a<102;a++)
for(b=0;b<102;b++)
map[a][b]=0;
int ans=0;
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
{
map[b][a]=input();
grass[b][a]=map[b][a];
}
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
if(map[b][a]>0)
{
ans--;
map[b][a]=ans;
map2(b,a,ans);
}
for(b=1;b<=n;b++)
for(a=1;a<=m;a++)
ans2[abs(map[b][a])]+=grass[b][a];
ans=abs(ans);
for(a=1;a<=ans;a++)
if(ans2[a]>max) max=ans2[a];
printf("%d\n%d\n",abs(ans),max);
}
return 0;
}