[規格9663]N-Queen C++

2058 ワード
白駿 アルゴリズム#アルゴリズム# テキストリンク

問題を理解する

  • 同一行、同一列、対角線を重ねることができない
    • .

    ソースコード

    #include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;

int col[110];
int N;
int result = 0;

bool promising(int i)
{
    int k=0;
	
	while (k<i) {
		if (col[i] == col[k] || abs(col[i] - col[k]) == i-k)
			{ return  false; }
		k++;
	}
	return true;
}
void queens(int i)
{
    if(i == N)
        result++;
    else {
        for(int j=0; j<N; j++) {
            col[i] = j;
            if(promising(i))
               queens(i+1);
        }
    }
}

int main()
{
    cin>>N;

    queens(0);

    cout<< result;

    return 0;
}
    パフォーマンスを向上させるには、セカンダリ・アレイと比較してプライマリ・アレイを使用します.
    最初はqueens(1)を使いましたが、結局値段が違いました.行と列は1からだと思っていたので関係ありません.
    考えてみたら、皇后(1)に置くと、最後の列はn.これにより,nに希望のqueens関数があるか否かを判断するにはelse文を通過できないため,得られる値は比較的少ない.
    [Laravel 6] Artisan command list customize
    反応成分におけるライフサイクル