Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<string,int> psi;
- typedef vector<int> vi;
- typedef vector<string> vs;
- typedef vector<ll> vll;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<string>> vvs;
- typedef vector<vector<ll>> vvll;
- #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
- #define FORd(i,b,a) for (int i =b; i >= a; i--)
- #define sz(x) (int)(x).size()
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define ins insert
- const int MOD = 1000000007;
- //type functions here
- bool mgs(int (&a)[9])
- {
- int d=0,b=0,c=0;
- FOR(i,0,2)
- {
- d+=a[i];
- b+=a[i+3];
- c+=a[i+6];
- }
- if(d!=b||b!=c)
- return false;
- d=0,b=0,c=0;
- for(int i=0;i<9;i+=3)
- {
- d+=a[i];
- b+=a[i+1];
- c+=a[i+2];
- }
- if(d!=b||b!=c)
- return false;
- int k=a[0]+a[4]+a[8],j=a[2]+a[4]+a[6];
- if(j!=k||k!=d)
- return false;
- return true;
- }
- int cost(int (&a)[9],vvi &v)
- {
- int ans=0,i=0;
- for(auto x:v)
- {
- for(auto y:x)
- {
- ans+=abs(a[i++]-y);
- }
- }
- //cout<<ans<<endl;
- return ans;
- }
- int mincost(vvi &v)
- {
- int a[9]={1,2,3,4,5,6,7,8,9};
- int m=INT_MAX;
- do{
- if(mgs(a)==true)
- { m=min(m,cost(a,v));
- /* for(int i=0;i<9;i+=3)
- {
- cout<<a[i]<<" "<<a[i+1]<<" "<<a[i+2]<<endl;
- }cout<<endl;*/
- }
- }while(next_permutation(a,a+9));
- return m;
- }
- int main() {
- vvi v={{5 ,3 ,4},{1, 5, 8},{6, 4, 2}};
- int m=mincost(v);
- cout<<m;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement