Uva208 Firetruck【dfs】【习题7-1】

题目：Firetruck

题意：输入一个n（n≤20）个结点的无向图以及某个结点k，按照字典序从小到大顺序输出从结点1到结点k的所有路径，要求结点不能重复经过。

思路：标准的dfs回溯。从1开始枚举每个点，可以通过的用一个数组记录，当达到k输出数组。每次递归要递归上一步的位置。

我只判断了其他点与k是否有直接连接，如果没有连接就说明达不到直接输出0，否则再搜索。

代码：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 21;int G[maxn][maxn],k,maxPoint,ans;int visit[maxn];void dfs(int steps,int location,int path[]){    if(location == k){        for(int i=0;i<steps-1;i++){            PRintf("%d ",path[i]);        }        printf("%d/n",path[steps-1]);        ans++;        return ;    }    for(int i=2;i<=maxPoint;i++){        if(G[location][i] && !visit[i]){           visit[i] = 1;           path[steps] = i;           dfs(steps+1,i,path);           visit[i] = 0;        }    }}int main(){    int u,v,kcase = 1;    while(scanf("%d",&k)!=EOF && k){        maxPoint = 0;        memset(G,0,sizeof(G));        while(scanf("%d%d",&u,&v) && (u || v)){            G[u][v] = G[v][u] = 1;            maxPoint = max(maxPoint,max(u,v));        }        ans = 0;        printf("CASE %d:/n",kcase++);        bool flag = 0;        for(int i=1;i<=maxPoint;i++)            if(G[k][i]) {flag = 1;break;}        if(flag){            memset(visit,0,sizeof(visit));            int path[maxn] = {1};            dfs(1,1,path);        }        printf("There are %d routes from the firestation to streetcorner %d./n",ans,k);    }    return 0;}