#include<iostream>
#include<memory.h>
using namespace std;
bool a[200];//标记是否走过
int b[200][200];
int n,m;
bool flag;
void dfs(int start,int count)
{
if(start==n-1)
{
flag=true;
return;
}
else if(start==n)
{
flag=false;
return;
}
else
{
for(int i=0;i<n;i++)
{
if(b[start][i]==0&&!a[i])
{
dfs(i,count+1);
a[i]=1;
}
}
}
}
int main(int argc, char **argv)
{
while(cin>>n&&n!=0)
{
cin>>m;
memset(a,false,sizeof(a));
memset(b,-1,sizeof(b));
int p,q;
for(int i=0;i<m;i++)
{
cin>>p>>q;
b[p][q]=0;
}
flag=false;
dfs(0,0);
if(flag)
{
cout<<"I can post the letter"<<endl;
}
else
{
cout<<"I can‘t post the letter"<<endl;
}
}
return 0;
}
思路:深度搜索每个城市是否存在道路,并用一个数组保存访问记录,识别能不能到达终点。
Sicily 1155. Can I Post the lette
原文:http://www.cnblogs.com/xlqtlhx/p/7554759.html