題目：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;}