Advertisement
Kali_prasad

form a magic square with less cost v1

Mar 28th, 2022
23
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef pair<string,int> psi;
  10. typedef vector<int> vi;
  11. typedef vector<string> vs;
  12. typedef vector<ll> vll;
  13. typedef vector<vector<int>> vvi;
  14. typedef vector<vector<string>> vvs;
  15. typedef vector<vector<ll>> vvll;
  16.  
  17. #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
  18. #define FORd(i,b,a) for (int i =b; i >= a; i--)
  19. #define sz(x) (int)(x).size()
  20. #define mp make_pair
  21. #define pb push_back
  22. #define f first
  23. #define s second
  24. #define ins insert
  25.  
  26. const int MOD = 1000000007;
  27. //type functions here
  28. bool mgs(int (&a)[9])
  29. {
  30.    
  31.     int d=0,b=0,c=0;
  32.     FOR(i,0,2)
  33.     {
  34.         d+=a[i];
  35.         b+=a[i+3];
  36.         c+=a[i+6];
  37.        
  38.     }
  39.     if(d!=b||b!=c)
  40.     return false;
  41.     d=0,b=0,c=0;
  42.     for(int i=0;i<9;i+=3)
  43.     {
  44.         d+=a[i];
  45.         b+=a[i+1];
  46.         c+=a[i+2];
  47.     }
  48.     if(d!=b||b!=c)
  49.     return false;
  50.     int k=a[0]+a[4]+a[8],j=a[2]+a[4]+a[6];
  51.     if(j!=k||k!=d)
  52.     return false;
  53.    
  54.     return true;
  55.    
  56.    
  57. }
  58. int cost(int (&a)[9],vvi &v)
  59. {
  60.    
  61.     int ans=0,i=0;
  62.     for(auto x:v)
  63.     {
  64.         for(auto y:x)
  65.         {
  66.             ans+=abs(a[i++]-y);
  67.         }
  68.     }
  69.     //cout<<ans<<endl;
  70.     return ans;
  71. }
  72. int mincost(vvi &v)
  73. {
  74.    
  75.     int a[9]={1,2,3,4,5,6,7,8,9};
  76.     int m=INT_MAX;
  77.     do{
  78.     if(mgs(a)==true)
  79.    { m=min(m,cost(a,v));
  80.      /*  for(int i=0;i<9;i+=3)
  81.        {
  82.            cout<<a[i]<<" "<<a[i+1]<<" "<<a[i+2]<<endl;
  83.        }cout<<endl;*/
  84.    }
  85.        
  86.     }while(next_permutation(a,a+9));
  87.     return m;
  88.    
  89. }
  90.  
  91.  
  92. int main() {
  93.    
  94.     vvi v={{5 ,3 ,4},{1, 5, 8},{6, 4, 2}};
  95.     int m=mincost(v);
  96.     cout<<m;
  97.     return 0;
  98. }
  99.  
  100.  
  101.  
  102.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement