e880. Q1 合影隊形

題目 Problem

題目連結：https://zerojudge.tw/ShowProblem?problemid=e880

敘述 Description

酷酷鯊是一支新成立的棒球隊，共有 $N$ 位球員。球隊裡原本氣氛融洽，大家都是好麻吉，同心協力爭取年度總冠軍。然而，最近一連串的比賽不順利，球員間開始出現摩擦。今天，棒球聯盟邀請了總統夫人到場開球。總統夫人是酷酷鯊隊的球迷，因此她希望能和全體球員合影留念。拍照時，球員們會站成一列。為了避免尷尬，球隊經理希望在安排拍照的隊型時，不要讓彼此有和芥蒂的球員站在一起。

舉例來說，如果有五位球員 A, B, C, D, E，其中 A 和 B 不願意站在一起，C 和 D 不願意站在一起，那麼 ABCDE 和 ABCED 不是適當的隊型，而 ACBDE 和 CADEB 則都是適當的隊型。

現在請你撰寫一個程式，協助球隊經理在總統夫人落臨之前，排出一個適當的合影隊型吧!

輸入 Input

第一行為球員人數 $N$，$N \leq 15$。（球員代號從 A 開始編起。）

第二行為有摩擦的球員配對數 $M$，$M \leq 50$。

第三行開始，每一行有兩個字元，代表有摩擦的兩個球員代號。兩個字元間以一個空格隔開。

輸出 Output

請輸出以字典遞增排序方式的第一個適合隊型。如果沒有任何適合隊型，請輸出 No Solution。計算時間不得超過2秒鐘。

範例輸入 Sample Input

範例1:
5 
2 
A B 
C D

範例2:
4 
4 
A B 
C D 
C A 
C B

範例輸出 Sample Output

範例1:
ACBDE

範例2:
No Solution

提示 Hint

題解 Solution

熟悉 STL 一定知道 next_permutation 可以直接窮舉
但是，直接窮舉 $15! = 1307674368000$ 種可能，沒辦法在 2 秒跑完（ZJ 直接開 1 秒）
必定要自己寫 DFS 剪枝了

用個 $15 \times 15$ 的矩陣紀錄他們能不能站在一起
DFS 時候 當前的成員 跟 前一個被選的成員，查詢能不能站在一起
可以就往下尋找，不能就可以直接找下一位成員

程式碼 Accepted Code

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/2/4
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000007LL;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int iNF = 0x3f3f3f3f;
// const ll MAXN = 

int N, M;
bool non[16][16] = {0};
bool judge = false;
bool visited[16] = {0};

void dfs(int now, string ans){
    if(now == N){
        cout << ans << '\n';
        judge = 1;
        return;
    }
    for(int i = 0; i < N && !judge; i++){
        if(!visited[i] && now && !non[ans[now - 1] - 'A'][i]){
            visited[i] = 1;
            string tmp = ans + (char)(i + 'A');
            dfs(now + 1, tmp);
            visited[i] = 0;
        }
        else if(!visited[i] && now == 0){
            visited[i] = 1;
            string tmp = ans + (char)(i + 'A');
            dfs(now + 1, tmp);
            visited[i] = 0;
        }
    }
}

/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> N >> M;
    while(M--){
        string aa, bb;
        cin >> aa >> bb;
        int a = aa[0] - 'A';
        int b = bb[0] - 'A';
        non[a][b] = non[b][a] = 1;
    }
    dfs(0, "");
    if(!judge)
        cout << "No Solution" << '\n';
    return 0;
}

後記 Afterword

一開始寫完以為會被 TLE，沒想到是直接 AC
然後交大程式寒訓因為武漢肺炎停辦 QAQ

之後再來寫一篇文，有關交大程式寒訓默哀文