Advertisement
Emiliatan

b510

Sep 4th, 2019
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. /* b510           */
  2. /* AC (0ms, 84KB) */
  3. #include <cstdio>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. const char Rook = 'R';
  9. const char Queen = 'Q';
  10. const char OnlyRook = 'O';
  11.  
  12. int M, N, cnt = 0;
  13. char chess[11][2];
  14.  
  15. void Search(int i, int Q, int R)
  16. {
  17.     if(i == M + N) { ++cnt; return; }
  18.  
  19.     char able_put[M + N];
  20.  
  21.     memset(able_put, 1, sizeof(able_put));
  22.  
  23.     for(int j = 0; j < i; ++j)
  24.     {
  25.         int posB = i - j + chess[j][1], posT = chess[j][1] - (i - j);
  26.         if(chess[j][0] == Rook)
  27.         {
  28.             able_put[chess[j][1]] = 0;
  29.             if(able_put[posB] == 1 && posB < M + N) able_put[posB] = OnlyRook;
  30.             if(able_put[posT] == 1 && posT >= 0) able_put[posT] = OnlyRook;
  31.         }
  32.         else if(chess[j][0] == Queen)
  33.         {
  34.             able_put[chess[j][1]] = 0;
  35.             if(able_put[posB] && posB < M + N) able_put[posB] = 0;
  36.             if(able_put[posT] && posT >= 0) able_put[posT] = 0;
  37.         }
  38.     }
  39.     for(int j = 0; j < M + N; ++j)
  40.     {
  41.         if(able_put[j] != 0)
  42.         {
  43.             chess[i][1] = j;
  44.             if(R > 0)
  45.             {
  46.                 chess[i][0] = Rook;
  47.                 Search(i + 1, Q, R - 1);
  48.                 chess[i][0] = 0;
  49.             }
  50.             if(able_put[j] != OnlyRook&&Q > 0)
  51.             {
  52.                 chess[i][0] = Queen;
  53.                 Search(i + 1, Q - 1, R);
  54.                 chess[i][0] = 0;
  55.             }
  56.             chess[i][1] = 0;
  57.         }
  58.     }
  59. }
  60. int main()
  61. {
  62.     for(; ~scanf("%d %d", &M, &N); cnt = 0)
  63.     {
  64.         memset(chess, 0, sizeof(chess));
  65.         Search(0, M, N);
  66.         printf("%d\n", cnt);
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement