AtCoder Grand Contest 041 C問題 - Domino Quality

Source

AtCoder Grand Contest 041
問題文

問題概要

省略

解法

省略

cLay（version 20191227-1）のコード

C++に変換後のコードはこちら

int N;

int ans[9][9][9], cnt;
int rc[10], cc[10];
char res[1000][1002];

int solve(int n, int r, int c){
  if(c==n) return solve(n,r+1,0);
  if(r==n){
    rep(i,n) if(rc[i] != 3) return 0;
    rep(i,n) if(cc[i] != 3) return 0;
    return 1;
  }

  rep(i,n) if(rc[i] > 3) return 0;
  rep(i,n) if(cc[i] > 3) return 0;

  if(ans[n][r][c] != -1) return solve(n,r,c+1);

  if(r+1 < n && ans[n][r+1][c] == -1){
    ans[n][r][c] = ans[n][r+1][c] = cnt++;
    rc[r]++;
    rc[r+1]++;
    cc[c]++;
    if(solve(n,r,c+1)) return 1;
    rc[r]--;
    rc[r+1]--;
    cc[c]--;
    cnt--;
    ans[n][r][c] = ans[n][r+1][c] = -1;
  }
  if(c+1 < n && ans[n][r][c+1] == -1){
    ans[n][r][c] = ans[n][r][c+1] = cnt++;
    rc[r]++;
    cc[c]++;
    cc[c+1]++;
    if(solve(n,r,c+1)) return 1;
    rc[r]--;
    cc[c]--;
    cc[c+1]--;
    cnt--;
    ans[n][r][c] = ans[n][r][c+1] = -1;
  }

  if(solve(n,r,c+1)) return 1;

  return 0;
}

{
  int r;
  rd(N);

  if(N==2) wt(-1), return 0;
  if(N==3){
    wt("aa.");
    wt("..a");
    wt("..a");
    return 0;
  }

  rep(n,4,8){
    rep(i,n) rep(j,n) ans[n][i][j] = -1;
    rep(i,n) rc[i] = cc[i] = 0;
    cnt = 0;
    solve(n,0,0);
  }

  rep(i,N) rep(j,N) res[i][j] = '.';
  r = N;
  while(r >= 8){
    r -= 4;
    rep(i,4) rep(j,4) if(ans[4][i][j] >= 0) res[r+i][r+j] = ans[4][i][j] + 'a';
  }
  rep(i,r) rep(j,r) if(ans[r][i][j] >= 0) res[i][j] = ans[r][i][j] + 'a';

  rep(i,N) wt(res[i]);
}

Current time: 2024年04月20日04時04分37秒
Last modified: 2019年12月29日00時05分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC041 AGC_C
トップページに戻る

Logged in as: unknown user (not login)