제출 #484544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484544		FatihSolak	Riddick's Cube (IZhO13_riddicks)	C++17	100 / 100	10 ms	316 KiB

riddicks

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n,m;
int ans = 1e9;
bool ck(vector<vector<int>> v){
    bool ok = 1;
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++){
            if(v[i][j] != v[i][j-1])ok = 0;
        }
    }
    if(ok)return 1;
    ok = 1;
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j] != v[i-1][j])ok = 0;
        }
    }
    return ok;
}
int calc(vector<int> v,vector<int> v2){
    int ret = 1e6;
    for(int x=0;x<m;x++){
        if(v == v2)ret = min(ret, min(x,m-x));
        int tmp = v[0];
        for(int i=0;i<m-1;i++){
            v[i] = v[i+1];
        }
        v[m-1] = tmp;
    }
    return ret;
}
void go(int a,vector<vector<int>> v,int cost){
    if(a == m){
        if(ck(v)){
            ans = min(ans, cost);
        }
        for(int x=0;x<m;x++){
            int costt = cost + min(x, m-x);
            for(int i=1;i<n;i++){
                costt += calc(v[i],v[0]);
            }
            ans = min(ans, costt);
            int tmp = v[0][0];
            for(int i=0;i<m-1;i++){
                v[0][i] = v[0][i+1];
            }
            v[0][m-1] = tmp;
        }
        return;
    }
    for(int i=0;i<n;i++){
        go(a+1,v,cost+min(i,n-i));
        int tmp = v[0][a];
        for(int i=0;i<n-1;i++){
            v[i][a] = v[i+1][a];
        }
        v[n-1][a] = tmp;
    }
}
void solve(){
    cin >> n >> m;
    vector<vector<int>> v;
    for(int i=0;i<n;i++){
        v.push_back({});
        for(int j=0;j<m;j++){
            int x;
            cin >> x;
            v[i].push_back(x);
        }
    }
    go(0,v,0);
    cout << min(ans,100500);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 100 / 100