博主歡迎轉(zhuǎn)載，但請給出本文鏈接，我尊重你，你尊重我，謝謝~
http://www.cnblogs.com/chenxiwenruo/p/6789810.html
特別不喜歡那些隨便轉(zhuǎn)載別人的原創(chuàng)文章又不給出鏈接的
所以不準偷偷復制博主的博客噢~~

?

一開始以為是八皇后問題，這不就需要狀態(tài)壓縮dp嘛，PAT沒想到竟然還會考這個
往后看才發(fā)現(xiàn)，原來只是判斷是否是八皇后問題的一個解而已。

很明顯，八皇后的一個解，每條行、列、對角線最多有1個皇后
所以for一遍的時候，相應行、列、對角線的個數(shù)++，如果有大于1的，那肯定就不是了。

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring>using namespace std; const int maxn=1000+5; int row[maxn]; int col[maxn]; int diagonal[maxn*2]; //diagonal[i]表示第i條對角線上是否有queen int n; int main() {int t;scanf("%d",&t);for(int i=0;i<t;i++){scanf("%d",&n);memset(row,0,sizeof(row));memset(col,0,sizeof(col));memset(diagonal,0,sizeof(diagonal));int r,c;bool flag=true;for(c=1;c<=n;c++){scanf("%d",&r);r=n-r+1;row[r]++;col[c]++;diagonal[r+c-1]++;if(row[r]>1)flag=false;if(col[r]>1)flag=false;if(diagonal[r+c-1]>1)flag=false;}if(flag)printf("YES\n");elseprintf("NO\n");}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenxiwenruo/p/6789810.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的PAT甲题题解-1128. N Queens Puzzle (20)-做了一个假的n皇后问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。