Firetruck
题目链接：
http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17347
题目大意：
消防车从起点1出发，到终点n。问有多少条路径（每个结点只能通过一次），将路径按照字典序输出。
首先是一副无向图，结点数最大为21。
如以下样例：
6 1 2 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0
表示6为着火处，有8条路可走，路以（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.
解题思路：
一开始直接从起点开始采用回溯法进行dfs深搜，但是TLE了。没有想到很好的解决方案，看了别人的结题报告，有一个很好的想法：双向搜索
即先从终点开始进行BFS，将所有能够到达的结点用一use数组标记。
然后再从起点开始DFS回溯进行深搜，只有之前被标记过的，且符合条件的才能搜，大大提高了效率。
代码：
/*
ID: wuqi9395@126.com
PROG: beads
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int g[25][25], vis[25], n, sum, b[25], use[25];
void dfs(int x, int t)
{
int i, j;
if (x == n)
{
for (i = 0; i < t - 1; i++)
printf("%d ", b[i]);
printf("%d\n", n);
sum++;
}
else for (i = 1; i <= 21; i++) if (use[i] && g[x][i] && !vis[i])
{
b[t] = i, vis[i] = 1;
dfs(i, t + 1);
vis[i] = 0;
}
}
void bfs()
{
int i, j;
mem(use, 0);
queue<int> q;
q.push(n);
use[n] = 1;
while(!q.empty())
{
int t = q.front();
q.pop();
for (i = 1; i <= 21; i++) if (!use[i] && g[t][i])
{
use[i] = 1;
q.push(i);
}
}
}
int main ()
{
int cas = 1;
while(scanf("%d", &n) != EOF)
{
mem(g, 0);
mem(vis, 0);
int u, v;
while(scanf("%d%d", &u, &v))
{
if (u + v == 0) break;
g[u][v] = g[v][u] = 1;
}
printf("CASE %d:\n", cas++);
sum = 0;
vis[1] = 1, b[0] = 1;
bfs();
dfs(1, 1);
printf("There are %d routes from the firestation to streetcorner %d.\n", sum, n);
}
return 0;
}