UVA-208 消防车 题解答案代码 算法竞赛入门经典第二版
GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
一道不难的DFS题目。
直接用DFS遍历会超时。要先遍历一遍连通图，看看1和终点是否联通。
这里有同学会问，遍历连通图也用的是DFS呀，为啥不会超时？因为我们要记录路径，所以DFS函数退出时要设置重新设置点为未访问过。但是连通图并不需要。所以连通图要快很多。
另外题目的输出样例不对。看起来是%4d或者\t，但实际上就是普通的单个空格，甚至最前面不用空。（可以参考代码）
AC代码
#include <stdio.h>
#include <string.h>
#define MAX 21int terminal;
int map[MAX][MAX];
int tempLine[MAX];
int totalLine[MAX][10000];
int totalNum = 0;
int findStatus[MAX];void copyLine(int *arr1, int *arr2)
{for (int i = 0; arr1[i]; ++i){arr2[i] = arr1[i];}
}// 初始化
void init()
{memset(map, 0, sizeof(map));memset(tempLine, 0, sizeof(tempLine));memset(totalLine, 0, sizeof(totalLine));memset(findStatus, 0, sizeof(findStatus));totalNum = 0;
}void dfs(int i, int num)
{tempLine[num] = i;findStatus[i] = 1;++num;if (i == terminal){copyLine(tempLine, totalLine[totalNum]);++totalNum;findStatus[i] = 0;return;}int x, y;for (x = 1; x < MAX; ++x){if (map[i][x] && !findStatus[x]){dfs(x, num);tempLine[num] = 0;}}findStatus[i] = 0;
}void findDfs(int i)
{findStatus[i] = 1;for (int x = 1; x < MAX; ++x){if (map[i][x] && !findStatus[x])findDfs(x);}
}int main()
{int x, y, i = 0;while (scanf("%d", &terminal) == 1){// 初始化init();++i;while (scanf("%d %d", &x, &y) == 2 && x != 0){map[x][y] = 1;map[y][x] = 1;}printf("CASE %d:\n", i);// 先求联通图findDfs(1);if (!findStatus[terminal]){printf("There are 0 routes from the firestation to streetcorner %d.\n", terminal);continue;}memset(findStatus, 0, sizeof(findStatus));dfs(1, 0);for (x = 0; x < totalNum; ++x){for (y = 0; totalLine[x][y]; ++y){if (y != 0)putchar(' ');printf("%d", totalLine[x][y]);}putchar('\n');}printf("There are %d routes from the firestation to streetcorner %d.\n", totalNum, terminal);}return 0;
}