[伯俊]9663号:N-Queen

6455 ワード
白駿 supin2 cpp テキストリンク
回答日:2021-09-18

質問する


質問リンク:https://www.acmicpc.net/problem/9663

アクセスと解析


これは私個人では解決しにくい後継問題です.
まず皇后の行為を理解しなければならない.
皇后は上、下、左、右、対角方向に歩くことができるので、いずれかの行に皇后を置く場合、その行、列、およびすべての対角方向に他の皇后を置くことはできません.
これらの事実を利用して実施した.
  • 最初の行からQueenを配置します.(コード内の1次元配列板変数のindexは行を表し、その値は列を表す.ex)board[1]==2はQueenが第1行第2列にあることを表す.)
    1-1. その場所にQueenを置くことができるかどうかを確認します.(isPossible関数)
    1-2. これで、前の行の後ろの位置を表示し、同じ列に表示できます(board[row]==board[i]).
    対角位置(abs(board[row]-board[i])=row-i)にあるかどうかを確認します.
  • がこのように行われたとき、N個の皇后がすべて置かれたときに、もう一つの皇后を置く方法を追加します.

    • コード#コード#

    // 백준 9663번 : N-Queen
#include <iostream>

using namespace std;

int N, ans = 0;
int board[16]; // idx : 행, 값 : 열

bool isPossible(int row) {
    for (int i = 0; i < row; i++) {
        if (board[row] == board[i] || (abs(board[row] - board[i]) ==  row - i )) {
            return false;
        }
    }
    return true;
}

void dfs(int row) {
    if (row == N) {
        ans++;
        return;
    }
    for (int col = 0; col < N; col++) {
        board[row] = col;
        
        if (isPossible(row)) {
            dfs(row + 1);
        }
    }
}

int main() {
    cin >> N;

    dfs(0);
    
    cout << ans;
    return 0;
}

    結果



    フィードバック


    少し難しかったので実現に時間がかかりました.難易度の高い問題ももっとやらなければならない.
    centos 7-aarch 64 yumソースの置き換え方法
    debian 6.06更新ソース(バックアップ)(補足:7.00)