UVA 00216 - Getting in Line

解題觀念

DFS

可以參考我的課程簡報：BFS & DFS
關於 DFS 的基本觀念可以參考我的這篇文章：Algorithm - DFS

題目敘述

在此架構中，電腦被連成一串，也就是除了兩端的電腦各只連接一部電腦之外，其餘的電腦都正好連接 2 部電腦，左圖中，黑點代表電腦，且他們的位置以平面座標來表示，2 部電腦間距離以呎為單位


現在我們需要使連接的網路線最短，這也就是你的任務，在架設網路線時，網路線在地板下，所以相連的2部電腦所需的網路線的長度為這2部電腦的距離再加上額外的16呎，右圖顯示了上圖電腦最佳的佈線方式
其總長度為：(4+16)+ (5+16) + (5.83+16) + (11.18+16) = 90.01呎

Input

輸入含有多組測試資料
每組測試資料的第一列有一個正整數 n（2 <= n <= 8），代表網路中電腦的數目，接下來的 n 列每列有 2 個介於 0 ~ 150 之間的整數，代表一部電腦的平面座標，沒有2部電腦會在同一位置
當 n = 0 代表輸入結束

// Sample Input
6
5 19
55 28
38 101
28 62
111 84
43 116
5
11 27
84 99
142 81
88 30
95 38
3
132 73
49 86
72 111
0

Output

每組測試資料以輸出一列 * 開始，然後列出布置網路線的長度，從一端到另一端（從哪一端開始都可以），最後再列出所需的總長度，各距離均輸出到小數點後2位

// Sample Output
**********************************************************
Network #1
Cable requirement to connect (5,19) to (55,28) is 66.80 feet.
Cable requirement to connect (55,28) to (28,62) is 59.42 feet.
Cable requirement to connect (28,62) to (38,101) is 56.26 feet.
Cable requirement to connect (38,101) to (43,116) is 31.81 feet.
Cable requirement to connect (43,116) to (111,84) is 91.15 feet.
Number of feet of cable required is 305.45.
**********************************************************
Network #2
Cable requirement to connect (11,27) to (88,30) is 93.06 feet.
Cable requirement to connect (88,30) to (95,38) is 26.63 feet.
Cable requirement to connect (95,38) to (84,99) is 77.98 feet.
Cable requirement to connect (84,99) to (142,81) is 76.73 feet.
Number of feet of cable required is 274.40.
**********************************************************
Network #3
Cable requirement to connect (132,73) to (72,111) is 87.02 feet.
Cable requirement to connect (72,111) to (49,86) is 49.97 feet.
Number of feet of cable required is 136.99.

Solution Code

#include<bits/stdc++.h>
using namespace std;

deque<int> x;
deque<int> y;

deque<int> x_now;
deque<int> y_now;

int n;
double shortest;

map<int, bool> flag;
deque<int> final_edge;

double calculate( int x1, int y1, int x2, int y2 ){
    
    // 計算兩點之間的距離
    // pow 次方 -> pow( 底數, 指數 )
    // sqrt 開根號 -> sqrt( 數 )
    return sqrt( pow( ( x1 - x2 ) , 2 ) + pow( ( y1 - y2 ) , 2 ) );

}

void dfs( int depth, double path ){

    if( depth == n ){
        if( path < shortest ){          
            shortest = path;
            final_edge.clear();

            for( int i = 0; i < n; i++ ){              
                final_edge.push_back( x_now[ i ] );
                final_edge.push_back( y_now[ i ] );
            }
        }
        return;
    }

    // 這次的 dfs 要對每個點做開關 ( true or false )
    // 在做完一趟後 直接更改 depth - 1 的點後 去對 depth 的點 ( 改變末兩點 )
    // 第二趟時 跟改 depth - 2 的點後 先依輸入順序填入後面其他點 而後下幾輪再繼續排列
    for( int i = 0; i < n; i++ ){

        if( flag[i] ){
            flag[i] = false;
            x_now[ depth ] = x[i];
            y_now[ depth ] = y[i];

            if( depth == 0 ){
                dfs( depth + 1, 0 );
            }
            else{
                dfs( depth + 1, path + 16 + calculate( x_now[ depth ], y_now[ depth ], x_now[ depth - 1 ], y_now[ depth - 1 ] ) );            
            }       
            flag[i] = true;
        }
    }
}

int main(){

    int num = 1;
    while( cin >> n && n ){

        int edge;

        // 先隨便設個最小值
        shortest = 2147483647;

        for( int i = 0; i < n; i++ ){

            cin >> edge;
            x.push_back(edge);

            cin >> edge;
            y.push_back(edge);

            flag.insert( pair<int, bool>( i, true ) );
        }

        dfs( 0, 0 );

        cout << "**********************************************************" << endl;
        cout << "Network #" << num << endl;

        for( int i = 0; i < ( 2 * n ) - 2; i += 2 ){
            cout << "Cable requirement to connect (" << final_edge[i] << "," << final_edge[ i + 1 ] << ") to (" << final_edge[ i + 2 ] << "," << final_edge[ i + 3 ] << ") is " << fixed << setprecision(2) << 16 + calculate( final_edge[i], final_edge[ i + 1 ], final_edge[ i + 2 ], final_edge[ i + 3 ] ) << " feet." << endl;
        }

        cout << "Number of feet of cable required is " << fixed << setprecision(2) << shortest << "." << endl;

        x.clear();
        y.clear();

        x_now.clear();
        y_now.clear();

        flag.erase( flag.begin(), flag.end() );
        final_edge.clear();

        num++;
    }
}