[C++] [ITSA竞赛题目][57-3] 乐活单车游

题目出自ITSA竞赛，解答仅供参考

题目连结: 乐活单车游

解答:

#include <stdio.h>#include <stdlib.h>bool search(int **map, int p, int currentCount, int count, int current, int end);int main(void){    int n = 0;    int p = 0;    int a = 0;    int b = 0;    scanf("%d", &n);    while (n > 0)    {        scanf("%d %d %d", &p, &a, &b);        //初始化阵列        int **map = new int *[p];        for (int i = 0; i < p; i++)        {            map[i] = new int[p];            for (int j = 0; j < p; j++)            {                map[i][j] = 0;            }        }        int count = 0;        int r = 0;        int s = 0;        while (true)        {            scanf("%d", &r);            if (r == -1)            {                break;            }            scanf("%d", &s);            map[r][s] = map[s][r] = 1;            count++;        }        if (search(map, p, 0, count, a, b))        {            printf("YES\n");        }        else        {            printf("NO\n");        }        n--;        //释放阵列        for (int i = 0; i < p; i++)        {            delete[] map[i];        }        delete[] map;    }    system("pause");    return 0;}//return       找到路线回传true//map          路线地图//p            路口数//currentCount 目前走完的路线数//count        总路线数//current      当前路口//end          终点路口bool search(int **map, int p, int currentCount, int count, int current, int end){    //成功走完所有路线回到终点    if (current == end && currentCount == count)    {        return true;    }    //走完所有路线但没有回到终点    if (currentCount == count)    {        return false;    }    //往下一个路口    for (int i = 0; i < p; i++)    {        if (map[current][i] == 1)        {            //将走过的路线移除            map[current][i] = map[i][current] = 0;            if (search(map, p, currentCount + 1, count, i, end))            {                //找到路线直接返回                return true;            }            //还原移除的路线            map[current][i] = map[i][current] = 1;        }    }    return false;}

说明:
路线图我使用二维阵列 map 储存，如下图:
map[a][b] = 1 代表 a 和 b 两路口相通，
map[a][b] = 0 代表 a 和 b 两路口不相通。

search 函数做图形的走访，这里我使用深度搜寻，走法如下图:
假设起点为2
2 -> 1
1 -> 0
0 -> 4
4 -> 1
这时发现没有路可以走了，原路返回到1，发现可以走4
1 -> 4
4 -> 0
0 -> 1
这时发现没有路可以走了，原路返回到1，因为 0,4 都已经走过，再继续返回到2
2 -> 3
PS.因箭头过多，所以省略中间部分 XD

if (current == end && currentCount == count){    return true;}

如果当前的路口在终点且所有路线都走完，表示成功找到解答。

if (currentCount == count){    return false;}

如果所有路线都走完但没有回到终点，表示此种走法不是解答，返回后继续搜寻。

if (map[current][i] == 1)

找下一个可以走的路线。

map[current][i] = map[i][current] = 0;...map[current][i] = map[i][current] = 1;

这里做了一个设计，只需将走过的两个路口设为不相通，就可以确保此路线不会被重複走过，此图形的路线为双向的，所以 a,b 和 b,a 都要设定，最后结束时要把路线还原，供下一次走访使用。

if (search(map, p, currentCount + 1, count, i, end)){    return true;}

题目不需要找出所有解，所以只要找到一个解就直接返回。

结语:
此题还蛮好玩的，需要一点图形走访的概念，本来想用堆叠来完成，但 include 找不到 stack 后来就放弃用递迴。