iT邦幫忙

0

[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 兩路口不相通。

https://ithelp.ithome.com.tw/upload/images/20171008/20106865xnL72lBwBO.jpg

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
https://ithelp.ithome.com.tw/upload/images/20171008/20106865bM0aI0QWt1.jpg

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 後來就放棄用遞迴。


尚未有邦友留言

立即登入留言