yukicoder No.861 - ケーキカット

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLayversion 20190820-1)のコード

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)

ログイン: