fork download
copy 
  1. /***>              @author : a_e_kasem              <***/
  2. //                        ﷽
  3. //                  { وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَى }
  4. //
  5. //         فَالجُهدُ يُثمِرُ إنْ تَضافَرَ صَفوُهُ، والعَزمُ يَرفعُ صَرحَ كُلِّ بُنيانِ
  6. //
  7. //                    وَما نَيلُ المَطالِبِ بِالتَمَنّي
  8. //                     وَلَكِن تُؤخَذُ الدُنيا غِلابا
  9. //                           ***
  10. //                   وَما اِستَعصى عَلى قَومٍ مَنالٌ
  11. //                   إِذا الإِقدامُ كانَ لَهُم رِكابا
  12. //
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. #define int long long
  17. #define cinAll(a) for (auto &it : a) cin >> it
  18. #define all(x) (x).begin(), (x).end()
  19. #define NO  void(cout << "NO\n")
  20. #define YES void(cout << "YES\n")
  21.  
  22.  
  23. const int N = 8;
  24. vector<vector<int>> board(N, vector<int>(N));
  25. bool col[N], diag1[2*N], diag2[2*N];
  26. vector<vector<int>> allSolutions;
  27. int testCase = 1;
  28.  
  29. void backtrack(int r = 0) {
  30.     if (r == N) {
  31.         vector<int> temp(N);
  32.         for (int i = 0; i < N; i++) {
  33.             for (int j = 0; j < N; j++) {
  34.                 if (board[i][j] == 1) temp[j] = i+1;
  35.             }
  36.         }
  37.         allSolutions.push_back(temp);
  38.         return;
  39.     }
  40.  
  41.     for (int c = 0; c < N; c++) {
  42.         if (!col[c] && !diag1[r - c + N] && !diag2[r + c]) {
  43.             col[c] = diag1[r - c + N] = diag2[r + c] = true;
  44.             board[r][c] = 1;
  45.             backtrack(r + 1);
  46.             board[r][c] = 0;
  47.             col[c] = diag1[r - c + N] = diag2[r + c] = false;
  48.         }
  49.     }
  50. }
  51.  
  52. void solve() {
  53.     int arr[N];
  54.     while (cin >> arr[0]) {
  55.         for (int i = 1; i < N; i++) cin >> arr[i];
  56.  
  57.         int minMove = 8;
  58.         for (auto &sol : allSolutions) {
  59.             int moves = 0;
  60.             for (int col = 0; col < N; col++)
  61.                 if (arr[col] != sol[col]) moves++;
  62.  
  63.             minMove = min(minMove, moves);
  64.         }
  65.  
  66.         cout << "Case " << testCase++ << ": " << minMove << "\n";
  67.     }
  68. }
  69.  
  70.  
  71. void FastIO();
  72. int32_t main() {
  73.     FastIO();
  74.     backtrack();
  75.     int t = 1;
  76.     cin >> t;
  77.     while(t--)
  78.     {
  79.         solve();
  80.     }
  81. }
  82.  
  83. void FastIO()
  84. {
  85.     ios::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.     cout.tie(nullptr);
  88. }
  89.  
  90.  
  91.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F7zaxT
language:
C++14 (gcc 8.3)
created:
11 hours 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!