2009-06-01 06:54:18來源不明
95北市資訊學科能力競賽 送愛心到肯大亞 (Care)
作法:DFS搜索節點
/****************************************************/
#include<stdio.h>#include<stdlib.h>
double map[21][21]={0},ans=1;
int n,start,end,flag[21]={0};
void DFS(int now,double sum)
{
int a;
if(now==end)
ans=ans*(1-sum);
for(a=1;a<=n;a++)
if(flag[a]==0&&map[now][a]!=0)
{
flag[a]=1;
DFS(a,sum*map[now][a]);
flag[a]=0;
}
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c;
for(a=1;a<=n;a++)
for(b=1;b<=n;b++)
scanf("%lf",&map[a][b]);
scanf("%d %d",&start,&end);
ans=1;
flag[start]=1;
DFS(start,1);
flag[start]=0;
printf("%.5lf\n",1-ans);
}
return 0;
}
下一篇:97北縣賽-4-金幣問題