| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 811 人关注过本帖
标题:这题是不是该用树做或者邻接矩阵做 盘达天神的植物
只看楼主 加入收藏
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
 问题点数:0 回复次数:2 
这题是不是该用树做或者邻接矩阵做 盘达天神的植物


盘达天神是位仁慈的天神,他掌管着许多个宇宙,他希望他的每个宇宙都是美丽富饶的,有一天他游历一个二维世界(描述为L x B的方格,每个方格或者是水,或者是土地)时,发现那个世界很贫脊,于是他散落了他随身携带的植物种子到每个土地格子上,希望它们能妆点这个二维世界,在伟大的盘达天神的神力影响下,这些植物是不会死的。 但是这些植物能长成一片吗?(相邻的两个格子都是植物则称它们属于同一片,相邻是指周围八个方向相邻,植物只能在土地上生长,不能在水中生长)


Input

第一行包含一个正整数T,表示有T组测试数据
每组测试数据第一行包含三个数正整数:L(0<L<=100),B(0<B<=100),N,表示二维世界的长和宽,N表示此世界中土地格子的数目,下面会有N行数据,每行包含两个整数X(1<=X<=L)和Y(1<=Y<=B),表示土地格子的坐标。未给出的格子为水。

Output

如果所有植物能长成一片,输出“yes”,否则输出“no”


Sample Input


2
3 3 5
1 1
1 3
2 2
3 1
3 3
3 3 6
1 1
1 2
1 3
3 1
3 2
3 3


Sample Output


yes
no

[此贴子已经被作者于2007-11-2 14:00:16编辑过]

搜索更多相关主题的帖子: 植物 天神 邻接矩阵 宇宙 方格 
2007-11-01 21:24
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
得分:0 

#include<stdio.h>
int a[100][100];
int l,b,n;
void f1(int,int);
int main()
{
int t,bq;
int i,j,k;
int x,y;
scanf("%d",&t);
for(k=0;k<t;k++)
{
for(i=0;i<100;i++)
for(j=0;j<100;j++)
a[i][j]=0;
scanf("%d%d%d",&l,&b,&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
}
a[x][y]=2;
f1(x,y);
bq=0;
for(i=0;i<l;i++)
for(j=0;j<b;j++)
if(a[i][j]==1)
bq=1;
if(bq==1)
printf("no\n");
else
printf("yes\n");
}
return 0;
}
void f1(int x,int y)
{
if(x-1>=0 && a[x-1][y]==1)
{
a[x-1][y]=2;
f1(x-1,y);
}
if(x-1>0 && y-1>0 && a[x-1][y-1]==1)
{
a[x-1][y-1]=2;
f1(x-1,y-1);
}
if(x-1>0 && y+1<b && a[x-1][y+1]==1)
{
a[x-1][y+1]=2;
f1(x-1,y+1);
}
if(x+1<l && a[x+1][y]==1)
{
a[x+1][y]=2;
f1(x+1,y);
}
if(x+1<l && y-1>0 && a[x+1][y-1]==1)
{
a[x+1][y+1]=2;
f1(x+1,y-1);
}
if(x+1<l && y+1<b && a[x+1][y+1]==1)
{
a[x+1][y+1]=2;
f1(x+1,y+1);
}
if(y-1>0 && a[x][y-1]==1)
{
a[x][y-1]=2;
f1(x,y-1);
}
if(y+1<b && a[x][y+1]==1)
{
a[x][y+1]=2;
f1(x,y+1);
}
}



前世五百次的回眸 才换来今生的擦肩而过
2007-11-03 09:24
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
简单的DPS

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2007-11-03 21:01
快速回复:这题是不是该用树做或者邻接矩阵做 盘达天神的植物
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.034868 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved