問題： 給定一個n*n的棋盤，棋盤中有一些位置不能放皇後。現在要向棋盤中放入n個黑皇後和n個白皇後，使任意的兩個黑皇後都不在同一行、同一列或同一條對角線上，任意的 兩個白皇後都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小於等於8。 輸入格式 輸入的第一行為一個整數n，表示棋盤的大小。 ...
問題： 給定一個n*n的棋盤，棋盤中有一些位置不能放皇後。現在要向棋盤中放入n個黑皇後和n個白皇後，使任意的兩個黑皇後都不在同一行、同一列或同一條對角線上，任意的
兩個白皇後都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小於等於8。
輸入格式
輸入的第一行為一個整數n，表示棋盤的大小。
接下來n行，每行n個0或1的整數，如果一個整數為1，表示對應的位置可以放皇後，如果一個整數為0，表示對應的位置不可以放皇後。
輸出格式
輸出一個整數，表示總共有多少種放法。
樣例輸入
4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
樣例輸出
2
樣例輸入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
0
分析：1.用一個二維數組構造出一個n*n的矩陣。
2.逐行選擇某個合適的坐標來放置所謂的黑或者白皇後（如果放了黑，下次就放白的）。
3.接著步驟2，放另一種皇後。
步驟二和步驟三的實現：
1 void dfs(int i,int q)//i是初始行 q指的是是否在某位置上放置皇後 2 { 3 for(int j=0;j<n;j++) 4 { 5 //不能放的或者已經放過的 6 if(s[i][j]==0||s[i][j]==2)//已經放過的是2 7 { 8 continue; 9 } 10 int flag=1;//預設可以放 11 int y1=j-1;//左上角的黑皇後 12 int y2=j+1;//右上角的黑皇後 13 for(int l=i-1;l>=0;l--) 14 { 15 //判斷同一列、斜線上是否有相同皇後（同行肯定不會有：從上到下進行的） 16 //同一列 17 if(s[l][j]==q)//判斷同一列上是否有相同的皇後 18 { 19 flag=0; 20 break; 21 } 22 //斜線 23 if(y1>=0&&s[l][y1]==q)//判斷左對角線上是否有 24 { 25 flag=0; 26 break; 27 } 28 y1--; 29 if(y2<n&&s[l][y2]==q) 30 { 31 flag=0; 32 break; 33 } 34 y2++; 35 } 36 if(flag) 37 { 38 s[i][j]=q;//放皇後 39 if(i<n-1) 40 { 41 dfs(i+1,q); 42 } 43 else 44 { 45 //黑皇後放完了，開始放白皇後； 46 //白皇後放完的話就是一種方法結束 47 if(q==2) 48 { 49 dfs(0,3); 50 } 51 else 52 { 53 count++; 54 } 55 } 56 s[i][j]=1;//複原開始下一次 57 } 58 } 59 }
現在用C來實現
（其實用啥都一樣，我不是太會用C++）
1 #include <stdio.h> 2 void dfs(int i,int q); 3 int s[13][13]; 4 int n,count=0; 5 int main(){ 6 scanf("%d",&n); 7 for(int i=0;i<n;i++) 8 { 9 for(int j=0;j<n;j++) 10 { 11 scanf("%d",&s[i][j]);//對矩陣賦值 12 } 13 } 14 dfs(0,2);//黑皇後 15 printf("%d",count); 16 return 0; 17 } 18 void dfs(int i,int q)//i=0 q=2 19 { 20 for(int j=0;j<n;j++) 21 { 22 //不能放的或者已經放過的 23 if(s[i][j]==0||s[i][j]==2)//已經放過的是2 24 { 25 continue; 26 } 27 int flag=1;//預設可以放 28 int y1=j-1;//左上角的黑皇後 29 int y2=j+1;//右上角的黑皇後 30 for(int l=i-1;l>=0;l--) 31 { 32 //判斷同一列、斜線上是否有相同皇後（同行肯定不會有：從上到下進行的） 33 //同一列 34 if(s[l][j]==q)//判斷同一列上是否有相同的皇後 35 { 36 flag=0; 37 break; 38 } 39 //斜線 40 if(y1>=0&&s[l][y1]==q)//判斷左對角線上是否有 41 { 42 flag=0; 43 break; 44 } 45 y1--; 46 if(y2<n&&s[l][y2]==q) 47 { 48 flag=0; 49 break; 50 } 51 y2++; 52 } 53 if(flag) 54 { 55 s[i][j]=q;//放皇後 56 if(i<n-1) 57 { 58 dfs(i+1,q); 59 } 60 else 61 { 62 //黑皇後放完了，開始放白皇後； 63 //白皇後放完的話就是一種方法結束 64 if(q==2) 65 { 66 dfs(0,3); 67 } 68 else 69 { 70 count++; 71 } 72 } 73 s[i][j]=1;//複原開始下一次 74 } 75 } 76 }
下麵是不正宗的C++
#include<iostream> using namespace std; int s[13][13]; int n; int count=0;//計數 void dfs(int i,int q)//i=0 q=2 { for(int j=0;j<n;j++) { //不能放的或者已經放過的 if(s[i][j]==0||s[i][j]==2)//已經放過的是2 { continue; } int flag=1;//預設可以放 int y1=j-1;//左上角的黑皇後 int y2=j+1;//右上角的黑皇後 for(int l=i-1;l>=0;l--) { //判斷同一列、斜線上是否有相同皇後（同行肯定不會有：從上到下進行的） //同一列 if(s[l][j]==q)//判斷同一列上是否有相同的皇後 { flag=0; break; } //斜線 if(y1>=0&&s[l][y1]==q)//判斷左對角線上是否有 { flag=0; break; } y1--; if(y2<n&&s[l][y2]==q) { flag=0; break; } y2++; } if(flag) { s[i][j]=q;//放皇後 if(i<n-1) { dfs(i+1,q); } else { //黑皇後放完了，開始放白皇後； //白皇後放完的話就是一種方法結束 if(q==2) { dfs(0,3); } else { count++; } } s[i][j]=1;//複原開始下一次 } } } int main() { cin>>n;//對n賦值 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>s[i][j];//對矩陣賦值 } } dfs(0,2);//黑皇後 cout<<count<<endl; return 0; }
結尾了，，有什麼不懂的私聊我，一起學習，一起進步。1186294207
