省略
省略
C++に変換後のコードはこちら
#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 <?= abs(s-2a);
if(a==0){
sel[0][0] = 1;
doit(a+C[0][0]);
return;
}
rep(i,N) rep(j,N) m[i][j] = 0;
rep(i,N) rep(j,N) 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;
}
rep(i,N) rep(j,N) if(m[i][j]) da[i][j] = 0;
}
{
int i, j;
rep(i,N) rd(C[i](N));
res = ll_inf;
rep(i,N) rep(j,N) s += C[i][j];
uf.malloc(N*N);
doit(0);
wt(res);
}
Current time: 2024年03月28日21時52分31秒
Last modified: 2019年08月21日06時07分44秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る
Logged in as: unknown user (not login)