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