菜雞解N皇后問題

菜雞能有什么好想法？暴力就完了，

題目

     在一張N?N的國際象棋棋盤上，放置N個皇后，使得所有皇后都無法互相直接攻擊得到，（皇后可以直接攻擊到她
 所在的橫行，豎列，斜方向上的棋子），現在輸入一個整數N，表示在N?N的棋盤上放N個皇后，請輸出共有多少種使
 得所有皇后都無法互相直接攻擊得到的方案數， 例如下面這樣的擺法，是4皇后的一個解 （1代表有皇后，0代表沒有）
													0 1 0 0
													0 0 0 1
													1 0 0 0
													0 0 1 0

輸入一個整數 N

輸出能使得在N?N的國際象棋棋盤上放置N個皇后，并且所有皇后都無法互相直接攻擊得到的方案數

樣例輸入

	樣例輸入1：
	4
	樣例輸入2：
	8

樣例輸出

	樣例輸出1
	2
	樣例輸出2
	92

暴力思路：
觀察規律感覺類似于全排列的變式，將全排列中數字出現的順序看作X坐標，數字大小為Y坐標，所有皇后的排列情況即可表示出來，
限制條件：皇后攻擊范圍為米字，從坐標中體現為X值、Y值不能相同，在過皇后坐標斜率為正負一的直線上不能有棋子，X、Y方向由于看作數字全排列問題則不可能相等故無需考慮，對于斜線上情況能夠相互攻擊的條件為X+Y=n或X-Y=m，兩棋子m或n相同，故兩棋子取到的m、n值不能相同，
代碼：

#include<stdio.h>
int n, num = 0;
char map[50][50];//象棋棋盤
bool b[50], c[50], d[50];//斜率為1的限制值 斜率為-1的限制值 行限制值
void dfs(int m)
{
    if (n == m)
    {
        num++;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!d[i] && !b[i + m] && !c[i - m + n])
        {
            map[m][i] = '1';
            d[i] = b[i + m] = c[i - m + n] = true;
            dfs(m + 1);
            d[i] = b[i + m] = c[i - m + n] = false;
            map[m][i] = '0';
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            map[i][j] = '0';
        }
    }
    dfs(0);
    printf("%d", num);
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246981.html

標籤：其他

上一篇：2020計算思維復習

下一篇：【MATLAB有趣玩法】如何使用matlab打開pdf、播放視頻等，這些都很easy~（教你學習ActiveX)