Data Structure Homework 1 - N 皇后問題變化版

題目

Input

輸入 M N K 三個數字，M N 表示棋盤大小，K 表示上面已經有的棋子數，接著輸入 K 列位置 X Y，表示在 (X,Y) 位置上預先放置了皇后，預先放置的皇后位置不重複，也不受路徑限制。

3 <= M, N <= 10
0 <= K <= M*N
0 <= X < M
0 <= Y < N

Output

輸出 P 表示最多還能再放 P 個皇后，接著輸出 P 列表示一組解中的每個皇后位置，可能不只一組解，但輸出一組解就好。

範例測資

Input

5 3 2
3 2
4 2

Output

1
0 0

心得

分解成三個步驟

計算最多還能放幾個皇后
這題會預先放置皇后，開兩個 Set 計算被預先佔用的行與列有多少，計算 min(M - 佔用行數, N - 佔用列數) ，可以得到一個不嚴謹的皇后數量上限。
判斷某個位置能不能放皇后
皇后的路徑是八方位，所以開了四個陣列紀錄有沒有皇后存在。
放置皇后
Backtracking + DFS，不斷尋找可以擺放下一個皇后的位置，直到滿足最大皇后數量，如果找不到就回溯上一步，換個位置再繼續找。

截圖

完整程式碼

#include<bits/stdc++.h>
using namespace std;

struct Loc {
    int x, y;
};

int m, n, limit;
bool placeX[100] = { false };
bool placeY[100] = { false };
bool placeSlash[100] = { false };
bool placeBackSlash[100] = { false };
vector<Loc> builtin, queens, maxQueens;

bool recursive(int startX) {
    for (auto x = startX; x < m; x++) {
        if (placeX[x]) {
            continue;
        }
        for (auto y = 0; y < n; y++) {
            Loc l = Loc {x, y};
            if (placeY[y] || placeSlash[x+y] || placeBackSlash[x-y+n-1]) {
                continue;
            }
            
            // place a queen
            placeX[x] = true;
            placeY[y] = true;
            placeSlash[x+y] = true;
            placeBackSlash[x-y+n-1] = true;
            queens.emplace_back(l);

            if (queens.size() > maxQueens.size()) {
                maxQueens.assign(queens.begin(), queens.end());
            }

            if (queens.size() == limit) {
                return true;
            }
            if (recursive(x+1)) {
                return true;
            }
            
            // revert
            placeX[x] = false;
            placeY[y] = false;
            placeSlash[x+y] = false;
            placeBackSlash[x-y+n-1] = false;
            queens.pop_back();
        }
    }
    return false;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int k, x, y;
    set<int> cntX, cntY;
    cin >> m >> n >> k;
    
    builtin.reserve(k);
    for (auto i = 0; i < k; i++) {
        cin >> x >> y;
        builtin.emplace_back(Loc {x, y});
        placeX[x] = true;
        placeY[y] = true;
        placeSlash[x+y] = true;
        placeBackSlash[x-y+n-1] = true;
        cntX.insert(x);
        cntY.insert(y);
    }

    if (m == n && m == 2) {
        limit = 1 - k;
    } else if (m == n && m == 3) {
        limit = 2 - k;
    } else {
        limit = min(m - cntX.size(), n - cntY.size());
    }

    if (limit <= 0) {
        cout << "0" << endl;
        return 0;
    }
    queens.reserve(limit);
    maxQueens.reserve(limit);
    recursive(0);

    cout << maxQueens.size() << endl;
    for (auto& it : maxQueens) {
        cout << it.x << ' ' << it.y << endl;
    }
}