SRM 568 div2 Med

問題概要

3つ以下の数字がある。1stepに数字のうち1つを-9でき、1つを-3でき、1つを-1できる。計算結果が0以下になったものは0と見なす。
全ての数字を0にするためのステップ数を最小化せよ。

制約

• 3つの数字はそれぞれ[1,60]。

解法

bfsする。
(メモ化再帰やDPでも解ける。)

コード

#define INF 1e9
typedef vector<int> Vec;

class MutaliskEasy {
public:
  int solve(Vec &x){
    queue<Vec> Q; Q.push(x);
    queue<int> step; step.push(0);
    int d[61][61][61];
    fill(d[0][0],d[0][0]+61*61*61,INF);
    d[x[0]][x[1]][x[2]] = 0;
    while(!Q.empty()){
      Vec v = Q.front(); Q.pop();
      int s = step.front(); step.pop();
      if(v[0]+v[1]+v[2] == 0){
        return s;
      }
      int arr[3] = {1,3,9};
      do{
        Vec nv(3);
        for(int i = 0 ; i < 3 ; i++){
          nv[i] = max(0,v[i]-arr[i]);
        }
        if(d[v[0]][v[1]][v[2]]+1 < d[nv[0]][nv[1]][nv[2]]){
          d[nv[0]][nv[1]][nv[2]] = d[v[0]][v[1]][v[2]]+1;
          Q.push(nv);
          step.push(s+1);
        }
      }while(next_permutation(arr,arr+3));
    }
    return -1;
  }
  int minimalAttacks(Vec x) {
    while(x.size() != 3){ x.push_back(0); }
    return solve(x);
  }
};