fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. #define ll long long
  6.  
  7. int ans = 0, null=20;
  8. int valid[8][8]={0}, num[8]={0};
  9.  
  10. void places(int i, int j, int value){
  11.   value = (value)? 1: -1;
  12.   for (int l = 0; l < 8; ++l) {
  13.     if(l+i < 8){
  14.       if(l+j < 8)
  15.         valid[l + i][l + j] += value;
  16.       if(j-l >= 0)
  17.         valid[l + i][j - l] += value;
  18.     }
  19.     if(i-l >= 0){
  20.       if(j-l >= 0)
  21.         valid[i - l][j - l] += value;
  22.       if(j+l < 8)
  23.         valid[i - l][j + l] += value;
  24.     }
  25.  
  26.     valid[i][l] += value;
  27.     valid[l][j] += value;
  28.   }
  29. }
  30.  
  31. void solve(int i, int j){
  32.   // Base
  33.   if(j == 8){
  34.     null = min(null, ans);
  35.     return;
  36.   }
  37.   if(ans == 0 && j == 7 && i == 6){
  38.     cout << "";
  39.   }
  40.   // Transition
  41.     // Column
  42.     if(i+1 < 8)
  43.       solve(i+1, j);
  44.  
  45.     // Row
  46.     if(!valid[i][j]){
  47.       places(i, j, 1);
  48.       if( num[j]-1 != i )
  49.         ans++;
  50.  
  51.       solve(0, j+1);
  52.  
  53.       places(i, j, 0);
  54.       if( num[j]-1 != i)
  55.         ans--;
  56.   }
  57. }
  58. int main(){
  59.   ios::sync_with_stdio(false);
  60.   cin.tie(nullptr), cout.tie(nullptr);
  61.  
  62.   int i = 0;
  63.   while(!cin.eof()) {
  64.     ans = 0, null = 20;
  65.     i++;
  66.  
  67.     for (int j = 0; j < 8; ++j) {cin >> num[j];}
  68.     memset(valid, 0, sizeof valid);
  69.  
  70.     solve(0, 0);
  71.     cout << "Case " << i << ": " << null << endl;
  72.   }
  73.   return 0;
  74. }
  75.  
  76.  
  77.  
  78. // ####################
  79. // ##### 3BcarenO #####
  80. // ####################
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 8
https://ideone.com/C0ZvQy
language:
C++14 (gcc 8.3)
created:
2 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!