题意:城市某个地方发生火灾,求消防队到该点可能的所有路径(有的街道需要修理不能经过)及总路径数.直接回溯TLE,
所以需要预处理下，把与终点直接或间接相关的所有点给挑出来，然后在这个路径上进行回溯.
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #define MAXN 22
5 using namespace std;
6
7 int end,route[MAXN],sum,n,m;
8 bool vis[MAXN],edge[MAXN][MAXN],conn[MAXN];
9
10 void dfs_init(int u) //预处理:逆向寻找与目的点相关联的点
11 {
12 conn[u]=true;
13 for(int v=1;v<=n;++v)
14 {
15 if(!conn[v] && edge[u][v])
16 dfs_init(v);
17 }
18 }
19
20 void dfs(int k,int j){//正向搜索目标点,k:当前结点,j:目标路径当前结点
21 if(k==end){
22 sum++;
23 for(int i=1;i<j-1;i++)
24 printf("%d ",route[i]);
25 printf("%d\n",route[j-1]);
26 }
27 for(int v=2;v<=n;v++){
28 if(conn[v]&&edge[k][v]&&!vis[v]){//借用逆向搜索结果来剪枝
29 route[j]=v;
30 vis[v]=true;
31 dfs(v,j+1);
32 vis[v]=false;
33 }
34 }
35 }
36
37 int main(){
38 int a,b,l,test=1;
39 while(scanf("%d",&end)==1){
40 memset(conn,false,sizeof(conn));
41 memset(edge,false,sizeof(edge));
42 memset(vis,false,sizeof(vis));
43 vis[1]=true;route[1]=1;
44 n=0;sum=0;
45 while(scanf("%d %d",&a,&b)==2){
46 if(0==a && 0==b) break;
47 l=a>b?a:b;
48 if(l>n) n=l;
49 edge[a][b]=edge[b][a]=true;
50 }
51 dfs_init(end);
52 printf("CASE %d:\n",test++);
53 dfs(1,2); //从结点1开始
54 printf("There are %d routes from the firestation to streetcorner %d.",sum,end);
55 }
56 return 0;
57 }