#pragma GCC optimize ("Ofast") #include using namespace std; void *wmem; template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16]={0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } inline void rd(int &x){ int k, m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(long long x){ char f[20]; int m=0, s=0; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } template inline S chmin(S &a, T b){ if(a>b){ a=b; } return a; } struct unionFind{ int M, N, *d; inline void malloc(const int n){ d = (int*)std::malloc(n*sizeof(int)); M = n; } inline void free(void){ std::free(d); } inline void walloc(const int n, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; } inline void init(const int n){ int i; N = n; for(i=0;i<(n);i++){ d[i] = -1; } } inline void init(void){ init(M); } inline int get(int a){ int k, t=a; while(d[t]>=0){ t=d[t]; } while(d[a]>=0){ k=d[a]; d[a]=t; a=k; } return a; } inline int connect(int a, int b){ if(d[a]>=0){ a=get(a); } if(d[b]>=0){ b=get(b); } if(a==b){ return 0; } if(d[a] < d[b]){ d[a] += d[b]; d[b] = a; } else{ d[b] += d[a]; d[a] = b; } return 1; } inline int operator()(int a){ return get(a); } inline int operator()(int a, int b){ return connect(a,b); } inline int& operator[](const int a){ return d[a]; } inline int sizeList(int res[]){ int i, sz=0; for(i=0;i<(N);i++){ if(d[i]<0){ res[sz++] = -d[i]; } } return sz; } } ; char memarr[96000000]; #define N 5 int C[N][N]; int sel[N][N]; int da[N][N]; int db[N][N]; long long res; long long s; unionFind uf; int chksel(int i, int j, int v){ if(i-1 >= 0 && sel[i-1][j]==v){ return 1; } if(i+1 < N && sel[i+1][j]==v){ return 1; } if(j-1 >= 0 && sel[i][j-1]==v){ return 1; } if(j+1 < N && sel[i][j+1]==v){ return 1; } return 0; } void doit(long long a){ int i, j, k, m[N][N], ok; k = -1; uf.init(N*N); for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0){ if(k==-1){ k = N*i+j; } if(i-1 >= 0 && sel[i-1][j]==0){ uf(N*i+j, N*i+j-N); } if(j-1 >= 0 && sel[i][j-1]==0){ uf(N*i+j, N*i+j-1); } } } } ok = 1; for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0 && uf(N*i+j)!=uf(k)){ ok = 0; } } } if(ok){ chmin(res, abs(s-2*a)); } if(a==0){ sel[0][0] = 1; doit(a+C[0][0]); return; } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ m[i][j] = 0; } } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(sel[i][j]==0 && da[i][j]==0){ if(chksel(i,j,1)==0){ continue; } sel[i][j] = 1; doit(a+C[i][j]); sel[i][j] = 0; da[i][j] = 1; m[i][j] = 1; } } } for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ if(m[i][j]){ da[i][j] = 0; } } } } int main(){ int i, j; wmem = memarr; for(i=0;i<(N);i++){ { int Lj4PdHRW; for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){ rd(C[i][Lj4PdHRW]); } } } res = 4611686016279904256LL; for(i=0;i<(N);i++){ for(j=0;j<(N);j++){ s += C[i][j]; } } uf.malloc(N*N); doit(0); wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20190820-1 // --- original code --- // #define N 5 // int C[N][N], sel[N][N], da[N][N], db[N][N]; // ll res, s; // unionFind uf; // // int chksel(int i, int j, int v){ // if(i-1 >= 0 && sel[i-1][j]==v) return 1; // if(i+1 < N && sel[i+1][j]==v) return 1; // if(j-1 >= 0 && sel[i][j-1]==v) return 1; // if(j+1 < N && sel[i][j+1]==v) return 1; // return 0; // } // // void doit(ll a){ // int i, j, k, ok; // int m[N][N]; // // k = -1; // uf.init(N*N); // rep(i,N) rep(j,N){ // if(sel[i][j]==0){ // if(k==-1) k = N*i+j; // if(i-1 >= 0 && sel[i-1][j]==0) uf(N*i+j, N*i+j-N); // if(j-1 >= 0 && sel[i][j-1]==0) uf(N*i+j, N*i+j-1); // } // } // ok = 1; // rep(i,N) rep(j,N) if(sel[i][j]==0 && uf(N*i+j)!=uf(k)) ok = 0; // if(ok) res