題目
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;
}
}