fork(1) download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MAXN 10
  5.  
  6. int ans_cnt;
  7. short Qcnt, Rcnt, Bcnt;
  8. short Board_Len, QRcnt;
  9.  
  10. short now_row[MAXN];   // 宣告成全域變數，只有當PutQR會用到
  11. short nslash[MAXN<<1]; //+0 - +9
  12. short pslash[MAXN<<1]; //-9 - +9
  13. bool Col[MAXN];        //+0 - +9
  14. bool Row[MAXN];        //+0 - +9
  15. short *NS=&nslash[0];  // x+y：/
  16. short *PS=&pslash[9];  // x-y：\
  17.  
  18. vector<short> Slash_memo; // 紀錄有『選項』的#NS
  19. vector<short> Slash_pick[MAXN<<1]; // 紀錄#NS的『選項』
  20.  
  21. // Row從(0,N-1)中選取QRcnt個當作Queen和Rook要放的#Row
  22. void New_QueenRookMap(int now,int st);
  23.  
  24. // 枚舉選取的Row依序放入Queen或是Rook
  25. void PutQueenRook(int nowR,int Q,int R);
  26.  
  27. // 將棋盤轉45度後枚舉#NS，對於每個#NS枚舉#PS
  28. // (未做)Cut-Branch：將奇偶數分開計算(因為不會互相干擾，證明請參考a682的動態規劃解法)
  29. void PutBishop(int now,int cnt);
  30.  
  31. int main(){
  32.   ios::sync_with_stdio(0),
  33.   cin.tie(0), cout.tie(0);
  34.  
  35.   while(cin>>Qcnt>>Rcnt>>Bcnt){
  36.  
  37.     QRcnt=Qcnt+Rcnt;
  38.     Board_Len=QRcnt+Bcnt;
  39.  
  40.     ans_cnt=0;
  41.     New_QueenRookMap(0,0);
  42.  
  43.     cout<<ans_cnt<<endl;
  44.   }
  45. }
  46. void New_QueenRookMap(int now,int st){
  47.   if(now==QRcnt){ // 已經「成功」選取QRcnt個#Row
  48.     // init
  49.     fill(Col,Col+Board_Len,0);
  50.     fill(NS,NS+(Board_Len<<1),0);
  51.     fill(PS-Board_Len,PS+Board_Len,0);
  52.     // 枚舉每個選取的Row依序放入Queen和Rook
  53.     PutQueenRook(0,Qcnt,Rcnt);
  54.     return;
  55.   }
  56.   for(short i=st;i<=Board_Len-QRcnt+now;i++)
  57.     now_row[now]=i,
  58.     New_QueenRookMap(now+1,i+1);
  59. }
  60. void PutQueenRook(int idxR,int Queen,int Rook){
  61.   if(idxR==QRcnt){
  62.     // init
  63.     for(short i=0;i<(Board_Len<<1);i++) // 清空每個#NS的選項
  64.       Slash_pick[i].clear();
  65.     fill(Row,Row+Board_Len,0); // 將PutQueenRook時的#Row標示為已經選取的狀態
  66.     for(short  i=0;i<QRcnt;i++)
  67.       Row[ now_row[i] ]=1;
  68.     // 枚舉棋盤的所有格子，對於『合法空格』依序分配到對應的#NS作為選項
  69.     for(int r=0;r<Board_Len;r++)
  70.       if(!Row[r])
  71.         for(int c=0;c<Board_Len;c++)
  72.           if(!Col[c] and !NS[r+c] and !PS[r-c])
  73.             Slash_pick[r+c].push_back(r-c);
  74.     // 紀錄有『選項』的#NS
  75.     Slash_memo.clear();
  76.     for(int i=0;i<(Board_Len<<1);i++)
  77.       if(Slash_pick[i].size())
  78.         Slash_memo.push_back(i);
  79.     PutBishop(0,Bcnt);
  80.     return;
  81.   }
  82.   short nowR=now_row[idxR];      // 根據now_row[idx]轉為目前是#Row
  83.   for(short i=0;i<Board_Len;i++) //枚舉每個Column，選擇沒被佔走的放上棋子
  84.     if(!Col[i]){
  85.       Col[i]=1;
  86.       // PutQueen：把兩側的對角線方程式數值設定成Board_Len
  87.       if(Queen>0 and !NS[nowR+i] and !PS[nowR-i]){
  88.         NS[nowR+i]=PS[nowR-i]=Board_Len;
  89.         PutQueenRook(idxR+1,Queen-1,Rook);
  90.         NS[nowR+i]=PS[nowR-i]=0;
  91.       }
  92.       // PutRook：把兩側的對角線方程式數值+1, 這樣回朔時-1
  93.       if(Rook>0 and NS[nowR+i]<Board_Len and PS[nowR-i]<Board_Len){
  94.         NS[nowR+i]++, PS[nowR-i]++;
  95.         PutQueenRook(idxR+1,Queen,Rook-1);
  96.         NS[nowR+i]--, PS[nowR-i]--;
  97.       }
  98.       Col[i]=0;
  99.     }
  100.  
  101. }
  102. void PutBishop(int idxS,int Bishop){
  103.   if(Bishop==0){ ans_cnt++; return; }
  104.   if(idxS+Bishop>Slash_memo.size()) return;
  105.   PutBishop(idxS+1,Bishop);
  106.   short nowS=Slash_memo[idxS];
  107.   for(short i=0;i<Slash_pick[nowS].size();i++)
  108.     if(!PS[ Slash_pick[nowS][i] ])
  109.       PS[ Slash_pick[nowS][i] ]=1,
  110.       PutBishop(idxS+1,Bishop-1),
  111.       PS[ Slash_pick[nowS][i] ]=0;
  112. }
  113.  
Success #stdin #stdout 1.26s 15240KB
comments (?)
stdin
copy 
0 0 8
1 0 7
0 1 7
stdout
copy 
22522960
22084888
22084888
https://ideone.com/EmgZnB
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!