0

## [C++] [ITSA競賽題目][57-3] 樂活單車遊

``````#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[a][b] = 1` 代表 a 和 b 兩路口相通，
`map[a][b] = 0` 代表 a 和 b 兩路口不相通。

search 函數做圖形的走訪，這裡我使用深度搜尋，走法如下圖:

2 -> 1
1 -> 0
0 -> 4
4 -> 1

1 -> 4
4 -> 0
0 -> 1

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;
``````

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