Posted on 2009-08-23 19:50
Uriel 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
搜索
这类的DFS做了好几道了。。终于感觉做起来轻松一点了。。
/**//* Problem: 3194 User: Uriel
Memory: 384K Time: 16MS
Language: C++ Result: Accepted */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ax[]=
{0,0,1,-1};
int ay[]={1,-1,0,0};
int i,j,n,x[110][110],s[110][250],f[110][110],k;
bool Jge()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i][j])return false;
}
}
return true;
}
int Pre(int x,int y)
{
if(x<=0 || x>n || y<=0 || y>n)
return 1;
else
return 0;
}
void DFS(int a,int b)
{
int j;
int tx,ty;
for(j=0;j<4;j++)
{
tx=ax[j]+a;
ty=ay[j]+b;
if(!Pre(tx,ty) && x[tx][ty]==i && !f[tx][ty])
{
f[tx][ty]=1;
x[tx][ty]=0;
DFS(tx,ty);
}
}
}
int main()
{
while(1)
{
scanf("%d",&n);
if(n==0)break;
memset(x,0,sizeof(x));
for(i=1;i<n;i++)
{
for(j=0;j<2*n;j++)
{
scanf("%d",&s[i][j]);
}
for(j=0;j<2*n;j+=2)
{
x[s[i][j]][s[i][j+1]]=i;
}
}
for(i=1;i<n;i++)
{
for(j=1;j<=n;j++)
{
if(!x[i][j])x[i][j]=n;
}
}
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(x[j][k]==i)
{
DFS(j,k);
}
}
}
}
if(Jge()==false)printf("wrong\n");
else
printf("good\n");
}
system("PAUSE");
return 0;
}
感觉大概套路就是这样了。。POJ 1562 3620 ...
菜鸟刚学搜索，不足之处还请路过的大牛们指教