ZeroJudge D324: 8 Queens Chess Problem

同題：UVa 00750 – 8 Queens Chess Problem

在西洋棋得棋盤中你可以放置8個皇后而且彼此都不衝突 (就是都不能吃到對方）。給你某一個皇后的位置，請你寫一個程式來輸出所有這樣可能的安排。

範例輸入範例輸出
輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列。每列有 2 個整數 ，代表其中一個皇后必須放置的位置。為了把棋盤標準化，我們定義棋盤最左上角的位置為 (1, 1）。所以下圖黑色方塊的位置為 (4, 6），代表第 4 列 (ROW），第 6 行 (COLUMN）。		對每一組測試資料請先輸出表頭。然後每一種解答一列，在這裡只輸出列的位置，行的位置則以這 8 個數字出現的順序表示。若以Sample Output第1組測試資料為例說明：第 1 種解答 8 個皇后的位置分別為 (1, 1)、(5, 2)、(8, 3)、(6, 4)、(3, 5)、(7, 6)、(2, 7)、(4, 8)。
如果有不只一種解答，請按照字典順序由小到大排列。測試資料間亦請輸出一空白列，請參考 Sample Output。
1
1 1		SOLN COLUMN
# 1 2 3 4 5 6 7 8

1 1 5 8 6 3 7 2 4
2 1 6 8 3 7 4 2 5
3 1 7 4 6 8 2 5 3
4 1 7 5 8 2 4 6 3
ZeroJudge D324 範例測資

解題思路

使用 DFS 的方式去測試每一排是否可以成為一種可能，把已經放置的皇后位置存到一個陣列中，每次要放新的皇后時要檢查陣列中的位置看看是否會被吃掉。

範例程式碼－ZeroJudge D324: 8 Queens Chess Problem

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

vector<pair<int, int>>queen;
vector<vector<pair<int, int>>>ans;

int horizontal[10] = {};
int y, x;


void DFS(const int row, vector<pair<int, int>>v, int *hor) {
    if (row == y) {
        DFS(row+1, v, hor);
        return;
    }
    if (row == 9) {
        ans.push_back(v);
        return;
    }
    for (int i = 1; i<=8; i++) {
        if (hor[i] != 0) continue;
        bool isOK = true;
        for (int j = 0; j<v.size(); j++) {
            //cout << row << " " << i << " " << v[j].first << " " << v[j].second << endl;
            if (v[j].first == i || abs(row-v[j].second) == abs(i-v[j].first)) {
                isOK = false;
                break;
            }
        }
        if(isOK) {
            v.push_back(make_pair(i, row));
            hor[i]++;
            DFS(row+1, v, hor);
            hor[i]--;
            v.pop_back();
        }
        //break;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++) {
        queen.clear();
        ans.clear();
        cin >> y >> x;
        queen.push_back(make_pair(x, y));
        for (int j = 1; j<=8; j++) horizontal[j] = 0;
        horizontal[x]++;
        DFS(1, queen, horizontal);
        cout << "SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n";
        vector<vector<int>>output;
        for (int j = 0; j<ans.size(); j++) {
            sort(ans[j].begin(), ans[j].end());
            vector<int>tmp;
            for (int k = 0; k<8; k++) tmp.push_back(ans[j][k].second);
            output.push_back(tmp);
        }
        sort(output.begin(), output.end());
        for (int j = 0; j<output.size(); j++) {
            cout << j+1 << "      ";
            for (int k = 0; k<8; k++) {
                cout << output[j][k] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
}

//ZeroJudge D324
//Dr. SeanXD
標籤

相關文章

發佈留言