UVa1262 - Password (水題)

題目大意：

給你兩個 5*6 的表格，尋找這兩個表格的第 n 個 column 一樣的字母。
輸出第 x 個組合(透過字典序順序排列)

分析：

明顯第一直覺就是排列組合，時間複雜度最多為 (6^4)，合理可接受範圍內。

我原本的做法是只記錄共同的字母，然後進行排列組合。 => 程式碼不好維護

參考他的寫法後，覺得很棒。雖然時間複雜度比較高，但比較好維護

用二維陣列紀錄 Array[A-Z][column]，易讀易維護。

看來我對於 C++ 還是不夠了解，沒辦法當機立下用最好、最易讀的解法

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int ax[30][7] = {} ;
int ay[30][7] = {} ;
vector<string> Ans;

void dfs(int j , string strAns){
    if(j == 5){
        Ans.push_back(strAns);
        return ;
    }
    for(int i = 0 ; i < 26 ; i++){
        if(ax[i][j] && ay[i][j])
            dfs(j+1 , strAns+ (char)('A' + i));

    }
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin) ;
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL

    int n , x ;
    string strLine ;
    cin >> n ;
    while(n--){
        Ans.clear();
        cin >> x ;
        for(int i = 0 ; i < 26 ; i++){
            for(int j = 0 ; j < 6 ; j++){
                ax[i][j] = 0;
                ay[i][j] = 0;
            }
        }

        for(int i = 0 ; i < 6 ; i++){
            cin >> strLine;
             for(int j = 0 ; j < strLine.length() ; j++){
                ax[strLine[j] - 'A'][j] = 1 ;
            }
        }
        for(int i = 0 ; i < 6 ; i++){
            cin >> strLine;
             for(int j = 0 ; j < strLine.length() ; j++){
                ay[strLine[j] - 'A'][j] = 1 ;
            }
        }

        dfs(0, "");
        if(Ans.size() < x)
            cout << "NO" << '\n' ;
        else
            cout << Ans[x-1] << '\n' ;
    }

    return 0;
}