某城市消防部门与交通部门合作维护反映当前城市街道状况的地图。在规定的某天里，一些街道将由于修复或施工而被关闭。消防队员需要能够选择从消防站到火警地点的不经过被关闭街道的路线。
城市被划分成为不重叠的消防区，每区设有一个消防站。当火警发生时，一个中央调度站向火警地点所在的消防站发出警报并向其提供一个从该消防站到火警地点的路线。
输入
城市的每个消防区有一个独立的地图。每张地图的街区用小于21的正整数标识。消防站总是在街区#1。输入文件包括一些测试项，代表在不同街区发生的不同的火警。测试项的第一行均表示离火警最近街区的编号。接下来若干行由用空格隔开的表示开放的街道所邻接的街区的正整数对组成。（例如，如果数对 4 7 是文件中的一行，那么街区4 和7 之间的街道是开放的。在街区4 和7 之间的路段上没有其他街区。）每个测试项的最后一行由一个0数。
输出
对于每个测试项，你的输出必须用数字来标识测试项（case #1, case #2，等等）。输出必须将每条路线列在不同的行上，街区按路线顺序依次写出。输出必须给出从消防站到火警地点的所有路线的总数。其中只包括那些不经过重复街区的路线（由于显而易见的理由，消防部门不希望他们的车子兜圈子）。不同测试项的输出必须出现在不同的行上。
输入样例：
6 1 2 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0 4 2 3 3 4 5 1 1 6 7 8 8 9 2 5 5 7 3 1 1 8 4 6 6 9 0 0
输出样例：
CASE #1: 1 2 3 4 6 1 2 3 5 6 1 2 4 3 5 6 1 2 4 6 1 3 2 4 6 1 3 4 6 1 3 5 6 There are 7 routes from the firestation to streetcorner 6. CASE #2: 1 3 2 5 7 8 9 6 4 1 3 4 1 5 2 3 4 1 5 7 8 9 6 4 1 6 4 1 6 9 8 7 5 2 3 4 1 8 7 5 2 3 4 1 8 9 6 4 There are 8 routes from the firestation to streetcorner 4.
简单搜索题。
代码：
#include<iostream> #include<cstring> #include<fstream> #include<vector> using namespace std; int maps[22][22],ans,vis[22],n,maxn=0; vector<int >V; void dfs(int x) { if(x==n) { ans++; vector<int >::iterator it; for(it=V.begin(); it!=V.end(); it++) { if(it!=V.begin())cout<<" "; cout<<*it; } cout<<endl; return ; } for(int i=1; i<=maxn; i++) if(i!=x&&maps[i][x]&&!vis[i]) { vis[i]=1; V.push_back(i); dfs(i); V.pop_back(); vis[i]=0; } } int main() { freopen("in","r",stdin); freopen("out","w",stdout); int loop=0; while(cin>>n) { int a,b; ans=maxn=0; memset(maps,0,sizeof(maps)); memset(vis,0,sizeof(vis)); while(cin>>a>>b&&a&&b) { maxn=max(maxn,max(a,b)); maps[a][b]=maps[b][a]=1; } if(loop)cout<<endl; cout<<"CASE #"<<++loop<<":"<<endl; V.clear(); vis[1]=1; V.push_back(1); dfs(1); cout<<"There are "<<ans<<" routes from the firestation to streetcorner "<<n<<"."<<endl; } }
运行结果：
