読者です 読者をやめる 読者になる 読者になる

AOJ 1110 Patience

問題文

5*4の20枚のカードがある(1~5)。あるカードと同じ数字の書いてあるカードが隣接(斜めでもよい)していれば、その二つのカードを取り出す。最適な取り出し方をした時、残るカードは何枚か

解法

幅優先探索で解く。状態をメモしておかないと状態数が爆発して、大変なことになるのと、resの初期値をINFにしてしまった。

コード

vii card(5, vi(4));
int N, dy[4] = {-1,0,1,1}, dx[4] = {1,1,1,0};

vii narrow(vii c){
  int t;
  rep(i, 5) rep(j, 4){
    if(j){
      if(c[i][j-1] != -1) continue;
      t = c[i][j-1]; 
      c[i][j-1] = c[i][j];
      c[i][j] = t;
    }else{
      if(i == 0) continue;
      if(c[i-1][3] != -1) continue;
      t = c[i-1][3];
      c[i-1][3] = c[i][j];
      c[i][j] = t;
    }
  }
  rep(i, 5) rep(j, 4){
    if(j){
      if(c[i][j-1] != -1) continue;
      t = c[i][j-1];
      c[i][j-1] = c[i][j];
      c[i][j] = t;
    }else{
      if(i == 0) continue;
      if(c[i-1][3] != -1) continue;
      t = c[i-1][3];
      c[i-1][3] = c[i][j];
      c[i][j] = t;
    }
  }
  return c;
}

int csize(vii origin){
  int ret = 0;
  rep(i, 5) rep(j, 4) if(origin[i][j] != -1) ret++;
  return ret;
}

int main(){
  scanf("%d", &N);
  while(N--){
    rep(i, 5) rep(j, 4) scanf("%d", &card[i][j]);

    map<vii, bool> m; // memo map 
    queue<vii>q;
    int res = 20;
    q.push(card);
    m[card] = true;
    while(!q.empty()){
      int qsize = (int)q.size();
      rep(i, qsize){
    vii c = q.front(); q.pop();
    rep(j, 5) rep(k, 4) rep(d, 4){
      vii n = c;
          int ny = j + dy[d], nx = k + dx[d];
      if(!BW(ny, 5) || !BW(nx, 4) || n[ny][nx] != n[j][k]) continue;
      n[ny][nx] = n[j][k] = -1;
      n = narrow(n);
      res = min(res, csize(n));
      if(m.count(n) == 0){
        m[n] = true;
        q.push(n);
      }
    }
      }
    }
    printf("%d\n", res);
  }
  return 0;
}