AtCoder Beginner Contest 224 D問題 - 8 Puzzle on Graph

Source

AtCoder Beginner Contest 224
問題文

問題概要

省略

解法

省略

cLay(version 20210926-1)のコード

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

int N = 9, M, X[40], Y[40], A[8];
int mat[9][9] = {}, pw10[9];
int qs = 0, qe = 0, q[4d5], mask, nx, emp;
HashMap<int,int> hs;

rd(M,(X--,Y--)(M),(A--)(N-1));
hs.init(4d5);
rep(i,M) mat[X[i]][Y[i]] = mat[Y[i]][X[i]] = 1;

pw10[0] = 1;
rep(i,1,N) pw10[i] = pw10[i-1] * 10;

mask = invDigit(N-1, A);
hs[mask] = 0;
q[qe++] = mask;

while(qs < qe){
  mask = q[qs++];
  if(mask == 76543210) wt(hs[mask]), return 0;
  DigitF(mask, N-1, A);
  emp = Mex(N-1, A);
  rep(i,N-1) if(mat[A[i]][emp]){
    nx = mask + (emp - A[i]) * pw10[i];
    if(hs.exist(nx) == 0){
      hs[nx] = hs[mask] + 1;
      q[qe++] = nx;
    }
  }
}
wt(-1);

Current time: 2021年12月05日22時20分35秒
Last modified: 2021年10月24日00時04分42秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC224 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: