ZeroJudge A524: 手機之謎

鄭學長的手機裡有不可告人的秘密，為了不被發現那些照片和簡訊，他小心翼翼地把手機上鎖了。
幸好，你是個會寫程式的天才，你能夠產生所有的密碼去嘗試，現在趕快動手吧！
噢！還有一件事，基於某些理由，你知道鄭學長的密碼沒有重覆的字。

範例測資

範例輸入範例輸出
EOF 輸入，每筆資料有一個 N (N <= 8)，代表鄭學長的密碼位數。輸出所有可能的密碼，依字典順序反向排列 (因為你覺得他的密碼應該在後半段）。
3
2		321
312
231
213
132
123
21
12

解題思路

使用遞迴將每一種數字加到字串中，需要注意的是不能有重複的數字，可以使用 Map 或 Set 來做判斷。當判斷到字串長度為 N 時，將字串轉為整數並存到一個陣列中，一樣要先判斷是否已經有存過一樣的數字了。最後使用 Sort 排序陣列之後從最後一項往前輸出即可。

範例程式碼－ZeroJudge A524: 手機之謎

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int N;
vector<int>ans;
map<int, int>MAP;

void hi(string str, map<int, int>exist)
{
    if (str.length() == N)
    {
        int tmp;
        if (str.length() == 1) tmp = int(str[0] - '0');
        else tmp = stoi(str);
        if (MAP[tmp] == 0)
        {
            ans.push_back(tmp);
            MAP[tmp]++;
            return;
        }
    }
    for (int i = 1; i<=N; i++)
    {
        if (exist[i] == 0)
        {
            exist[i]++;
            hi(str+to_string(i), exist);
            exist[i]--;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N)
    {
        string str = "";
        map<int, int>h;
        hi(str, h);
        sort(ans.begin(), ans.end());
        for (int i = int(ans.size())-1; i>=0; i--)
        {
            cout << ans[i] << "\n";
        }
        ans.clear();
        MAP.clear();
    }
}

//ZeroJudge A524
//Dr. SeanXD
標籤

相關文章

發佈留言