# 枚舉
{%hackmd @themes/dracula %}

## 何謂枚舉
* 把所有可能性找出來
* 最慢、最直接的方法（暴力法）

> APCS p3, p4 的第一個子題通常能用枚舉偷分

## 常見方法
* 迴圈
* 遞迴
* 二進制

## 迴圈
* 就是全部跑一次

### 例題
#### 有幾個6
獨眼怪想知道 0~N 的數字裡面，共有幾個數字 6 在各個數字其中。

**INPUT**
輸入一個數字 N (N<=106)。

**OUTPUT**
輸出 0~N 中 6 的個數。

:::spoiler AC code

#include <iostream>
using namespace std;

int count_six(int n){
    int count = 0;
    while(n > 1){
        if(n % 10 == 6){
            count += 1;
        }
        n /= 10;
    }
    return count;
}

int main(){
    int n, s = 0;
    cin >> n;
    if(n < 6) cout << 0;
    else{
        for(int i = 6; i <= n; i++){
            s += count_six(i);
        }
        cout << s;
    }
}

:::

## 遞迴

### 例題
#### 獨眼怪試密碼
獨眼怪忘記自己保險庫的密碼了！
他只記得密碼共N個數字，且都介於0~M 之間。

**INPUT**
輸入只有一行 N, M (2<=N<=10, 1<=M<=9) 。

**OUTPUT**
請依照字典序輸出所有密碼可能讓獨眼怪參考。

:::spoiler AC code

#include <iostream>
using namespace std;

int n, m, ans[15];

void find(int pos){
    if(pos == n){
        for(int i = 0; i < n; i++) cout << ans[i];
        cout << "\n";
        return;
    }
    for(int i = 0; i <= m; i++){
        ans[pos] = i;
        find(pos+1);
    }
}

int main(){
    cin >> n >> m;
    find(0);
}

:::

## 二進制（子集合）

* 枚舉所有子集合的可能性
* 挑選東西 => 選 / 不選
* 分成兩種可能性，往下遞迴
* 複雜度：O(2^n)

### 例題
#### 分蘋果
有 N 顆蘋果裝在袋子裡，每顆蘋果都有甜美度，獨眼怪想要把它分成兩堆(其中一堆可以0顆)，使得這兩堆得蘋果甜美度相差最少。

**INPUT**
輸入有兩行，第一行為正整數 N(N≤20)，代表有幾顆蘋果。
第二行為 N 個整數代表甜美度，甜美度≤100。

**OUTPUT**
請輸出兩堆蘋果甜美度最少會差多少?

#### 想法
* 把全部的情形都舉出來就好了
:::spoiler AC code

#include <iostream>
using namespace std;

int n, a[25], s = 0, ans = 10000;

void comb(int sum1, int id){
    if(id == n){
        int sum2 = s - sum1;
        ans = min(ans, abs(sum1 - sum2));
        return;
    }
    comb(sum1 + a[id], id+1); // 拿
    comb(sum1, id+1); // 不拿
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        s += a[i];
    }
    comb(0, 0);
    cout << ans;
}

:::

## 剪枝

### 何謂剪枝
* 一種想法
* 遞迴過程中，如果繼續遞迴下去也不可能是答案，那就直接`return`

## 例題

### p4. 數獨

輸入一個 9∗9 的數獨，如果數字是0代表還沒填入數字。
請找到字典序最小的解

**INPUT**
輸入有9行，每行有9個數字，數字之間用空格隔開

**OUTPUT**
輸出字典序最小的解，保證一定有解

#### 想法
* 終止條件：填到最後一格

:::spoiler AC code

#include <iostream>
using namespace std;

int board[9][9];

bool check(int x, int y, int num) { // 檢查

    for (int i = 0; i < 9; i++) { // 橫的和直的
        if (board[x][i] == num || board[i][y] == num) {
            return false;
        }
    }

    int startX = (x / 3) * 3;
    int startY = (y / 3) * 3;
    for (int i = startX; i < startX + 3; i++) { // 小正方形
        for (int j = startY; j < startY + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }

    return true;
}

bool solve(int x, int y) {
    if (x == 9) {
        return true;
    }

    int nx = x, ny = y + 1;
    if (ny == 9) { // 檢查下一格有沒有要換行
        nx++;
        ny = 0;
    }

    if (board[x][y] != 0) { // 如果已經有答案就接下一個
        return solve(nx, ny);
    }

    for (int num = 1; num <= 9; num++) { // 每個數字都試過
        if (check(x, y, num)) {
            board[x][y] = num; // 填進去
            if (solve(nx, ny)) { // 如果這格這樣填下一格可以就一個遞迴安餒
                return true;
            }
            board[x][y] = 0; // 回復
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> board[i][j];
        }
    }

    if (solve(0, 0)) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << board[i][j];
                if(j < 8) cout << " ";
            }
            cout << "\n";
        }
    }
}

:::

### p5. N-Queen

給你一個大小為 N∗N 的棋盤，你要在上面擺皇后
我們稱一個 N∗N 的盤面合法的條件如下:
1.對於任兩個皇后，橫、直、斜的不能相互連線 (詳情觀察範例測資)
2.共要擺放 N 個皇后

**INPUT**
輸入僅有一個正整數 N(≤10) 代表棋盤大小為 N∗N。

**OUTPUT**
請輸出所有合法盤面，並輸出解法數，依照字典序大小輸出，皇后為Q，空格為x。
輸出格式詳見範例輸出，所有合法盤面之後皆須接一個空行。

#### 想法
* 終止條件：擺滿了n個皇后

:::spoiler AC code

#include <iostream>
using namespace std;

int n, board[15][15], cnt = 0, solutions = 0;

bool check(int x, int y){
    for(int i = 0; i < n; i++){
        if(board[x][i] == 1 || board[i][y] == 1) return false;
    }
    for(int i = x, j = y; i >= 0 && j >= 0; i--, j--){
        if(board[i][j]) return false;
    }
    for(int i = x, j = y; i < n && j < n; i++, j++){
        if(board[i][j]) return false;
    }
    for(int i = x, j = y; i >= 0 && j < n; i--, j++){
        if(board[i][j]) return false;
    }
    for(int i = x, j = y; i < n && j >= 0; i++, j--){
        if(board[i][j]) return false;
    }
    return true;
}

void solve(int x){
    if(cnt == n){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 1) cout << "Q";
                else cout << "x";
            }
            cout << "\n";
        }
        cout << "\n";
        solutions++;
    }
    for(int i = 0; i < n; i++){
        if(check(x, i)){
            board[x][i] = 1;
            cnt++;
            solve(x + 1);
            board[x][i] = 0;
            cnt--;
        }
    }
}

int main(){
    cin >> n;
    solve(0);
    cout << solutions;
}

:::

### p6. 字串MEX

給你一個僅由小寫英文字母構成的字串 S，你想知道這個字串的 MEX。
一個字串的 MEX 定義是:
1.最短且未出現在字串 S 當中的小寫英文字串。
2.如果有多個一樣短的小寫英文字串未出現在字串 S 請輸出字典序最小的。

**INPUT**
輸入第一行為一個整數 T(≤1000) 代表有 T(≤1000) 筆測資。
每筆測資有兩行，第一行為一個整數 N(N≤1000) 代表字串長度。
第二行為一個字串 S。

**OUTPUT**
請輸出其中一種解，結尾不要空格。

#### 想法
* 枚舉字串長度，由短到長

:::spoiler AC code

#include <iostream>
#include <string>
using namespace std;

int n;
string s;

bool check(string r){ // 剪枝
    int len = r.size();
    for(int i = 0; i < n-len+1; i++){
        if(r == s.substr(i, len)) return false;
    }
    return true;
}

bool search(int len, string now=""){
    if(len == int(now.length())){
        if(check(now)){
            cout << now << '\n';
            return true;
        }
        else return false;
    }
    for(char c = 'a'; c <= 'z'; c++){
        now += c;
        if(search(len, now)){
            return true;
        }
        now.pop_back();
    }
    return false;
}

void solve(){
    for(int i = 1; i <= n; i++){ // 枚舉長度 1~n 的字串
        if(search(i)){
            return;
        }
    }
}

int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n >> s;
        solve();
    }
}

:::

## 結語
### 解題過程
1. 確定枚舉對象、枚舉範圍和判定條件
2. 終止條件！！
3. 枚舉可能的解
4. 驗證，不合就剪掉