【検索】N皇后問題

1255 ワード

原題転送ゲート
構想
古典的な検索問題ですが、本こんにゃくは1時間以上詰まっていて、検索部分は簡単ですが、判定部分は本当に卵が痛くて、効率的な判定アルゴリズムを書きましたが、何度チェックしても問題のないアルゴリズムはいつもWAです・・それから私はいっそ超簡単だが遅いアルゴリズムを書いた.そして、過ぎた???このデータは水が酷いのでしょうか・・・こんなことを知っていたのに、ハイエンドのアルゴリズムを押すのに苦労して何をしているんだ......
Code

/*int r(int h,int l)
{
    int i;
    for(i=1;i0&&a[i][i-h+l]==1)
            return 0;
    }
    return 1;
}*/

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[15][15],ans;

int r(int h,int l)
{
    for(int i=1; i0&&j>0; i--,j--)
        if(a[i][j] == 1)
            return false;
    for(int i=h-1,j=l+1; i>0&&j<=n; i--,j++)
        if(a[i][j] == 1)
            return false;
    return true;
}

void dfs(int h)
{
    if(h==n+1)
    {
        ans++;
        return;
    }   
    int l;
    for(l=1;l<=n;l++)
    {
        a[h][l]=1;
        if(r(h,l))
            dfs(h+1);
        a[h][l]=0;
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<

線形テーブルLがインクリメントされていることが知られている.線形テーブルLの秩序性を維持するために、XをLの適切な位置に挿入するアルゴリズムを書きます.

JavaScript設計モードのポリシーモードを学ぶ