前言

今天有兩題相關題目，一題是最簡單的應用，另一題算是經典題，希望大家可以更熟悉 DFS 的應用與如何撰寫

UVa 441 - Lotto

題目說明

給定多個數字，要找出多個數字的所有彩券組合（6 個數字）

解題思路

要找出所有組合的話那就思考到暴力搜尋，或是如果記得昨天的內容應該也會記得 DFS 可以列出所有組合，因此可以很直觀的利用 DFS 把這一題解掉

AC Code

#include <bits/stdc++.h>
using namespace std;
long long a[15],ans[15];
void dfs(int d,int s,int k){
    if(d == 6){
        cout << ans[0];
        for(int i = 1;i < 6;i++){
            cout << " " << ans[i];
        }
        cout << "\n";
        return;
    }
    for(int i = s;i < k;i++){
        ans[d] = a[i];
        dfs(d + 1,i + 1,k);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long k,t = 0;
    while(cin >> k && k){
        if(t++){
            cout << "\n";
        }
        for(int i = 0;i < k;i++){
            cin >> a[i];
        }
        dfs(0,0,k);
    }
    return 0;
}

UVa 216 - Getting in Line

題目說明

有多個座標點，分別是各台電腦的座標，現在要使每台電腦串成一串，並且要使布置網路線的長度最短，另外，需要注意的是要將每一段的長度都算出來，最後再加總

解題思路

可以發現這是非常經典的一筆劃問題，需要列出各個結果再取出最好的，因此其實就是列出各種組合，所以也是可以用 DFS 解出來，需要注意的是要記住最好的組合

AC Code

#include <bits/stdc++.h>
using namespace std;
long long ans[10][2],n,a[10][2],aa[10][2];
bool u[20];
double m;
void dfs(int d){
    if(d == n){
        double len = 0;
        for(int i = 1;i < n;i++){
            len += sqrt(pow(aa[i][0] - aa[i - 1][0],2) + pow(aa[i][1] - aa[i - 1][1],2));
        }
        if(len < m){
            m = len;
            for(int i = 0;i < n;i++){
                ans[i][0] = aa[i][0];
                ans[i][1] = aa[i][1];
            }
        }
        return;
    }
    for(int i = 0;i < n;i++){
        if(!u[i]){
            u[i] = true;
            aa[d][0] = a[i][0];
            aa[d][1] = a[i][1];
            dfs(d + 1);
            u[i] = false;
        }
    }
}
int main(){
    long long t = 1;
    while(cin >> n && n){
        m = 3000000000000;
        for(int i = 0;i < n;i++){
            cin >> a[i][0] >> a[i][1];
        }
        dfs(0);
        cout << "**********************************************************\nNetwork #" << t++ << "\n";
        for(int i = 1;i < n;i++){
            double len = sqrt(pow(ans[i - 1][0] - ans[i][0],2) + pow(ans[i - 1][1] - ans[i][1],2));
            cout << fixed << setprecision(2) << "Cable requirement to connect (" << ans[i - 1][0] << "," << ans[i - 1][1] << ") to (" << ans[i][0] << "," << ans[i][1] << ") is " << len + 16 << " feet.\n";
        }
        cout<<"Number of feet of cable required is " << m + (n - 1) * 16 << ".\n";
    }
    return 0;
}

總結

今天兩題都是簡單不過又可以熟悉 DFS 的應用與實作的題目，不過或許會有人問為什麼不用 next_permutation() 這個函式，原因是因為我覺得 DFS 還是要自己實作過，畢竟每一種題目不太一樣，許多題目還是得需要自行撰寫，next_permutation() 的實用度未必高