中心城市消防部门与运输部门合作,维护反映城市街道现状的城市地图。消防员需要能够选择从火警站到火警的路线。 中心城市分为不重叠的消防区。当报告发生火灾时,中央调度员通知火灾发生地区最近的火警站,并列出可能路线。您必须编写一个程序,中央调度员可以使用该程序来生成从地区火警站到火灾的路线。
消防区都用小于 21 的正整数来标识,而且火场始终位于第一个消防区。输入文件包含多个测试用例,代表不同火灾。
• 测试用例的第一行由一个整数组成,该整数是距离火灾最近的火警站。
• 接下来的几行由成对的正整数组成,这些成对的正整数是开放街道相邻的消防区。(例如,如果对 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 <cstdio>
using namespace std;
const int maxn=21+4;
int map[maxn][maxn]={0};//用来存储地图
int mark[maxn];//用来记录走过的点,以便输出
bool m[maxn];//用来记忆该点有没有被访问过
int n,ans1;//ans1记录总共有多少条路径
void dfs(int x,int ans)//x表示所在的地点,ans表示这是去到的第几个地点
{
if(x==n)
{
ans1++;
cout<<'1';
for(int i=1;i<ans;i++)
cout<<' '<<mark[i];
cout<<endl;return ;
}
for(int i=2;i<maxn;i++)//从2开始逐个搜索,因为是从1出发,不能再回到1
if(map[x][i]==1&&!m[i])//如果i点与x点连通,而且i点没被访问过
{
mark[ans]=i;m[i]=true;
dfs(i,ans+1);
m[i]=false;
}
return ;
}
int main()
{
//freopen("text.txt","r",stdin);//文件输入
int cnt=1;
while(cin>>n)
{
memset(map,0,sizeof(map));//一轮下来,有些数据要被重置
int x=1,y=1;
ans1=0;//重置
while(true)
{
cin>>x>>y;
if(x==0||y==0)break;
map[x][y]=map[y][x]=1;//构建矩阵地图
}
cout<<"CASE "<<cnt++<<":"<<endl;
dfs(1,1);
cout<<"There are "<<ans1<<" routes from the firestation to streetcorner "<<n<<"."<<endl;
}
return 0;
}
void check(int x)
{
fir[x]=true;
for(int i=2;i<maxn;i++)
if(map[x][i]&&!fir[i])
check(i);
}
//还要每次用memset(fir,false,sizeof(fir));重置
//在dfs前调用check()函数
//dfs的条件改成if(map[x][i]==1&&!m[i]&&fir[i])