AOJ1512 Smartphone Game

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1512

パズドラを1回だけシミュレートせよ。ただし、移動可能回数は高々N回までである。
0 <= N <= 5
グリッドは5*5

解法
基本方針は高々N回DFSしてマスをswapしていき、各々の深度で消滅と落下をシミュレートする。よくある問題。

実装が自明でないなら、漫然と実装してはならず、如何にミスを避けて書くかを考える。

グリッドの状態は各深度で異なり、5*5とマスが少ないので、グリッドは配列ではなくvectorやarrayにして関数の引数とするのが良い。落下処理など別関数で変更したいときは参照渡し、移動を繰り返したいなら値渡しといった融通がきく。

（ミスしやすい前提で）ミスを減らしたいなら、各処理の関数化は必須。また、書く前にどこがミスしやすいか想定して、同時にデバッグやテストの方法も考えたい。

消す処理のデバッグ方法を考える。入力はサンプルを利用して、1回消すごとに状態を出力するのは再帰の深度を考えると面倒。
また、サンプルの入力を利用するのは「正しく消せているか？」を見るだけの単純な処理には向かない可能性がある。よって、自明に1個の塊だけ消せる、1個の塊も消せない、などのサンプルをて入力で作ることから始めて、必要であれば、自明な連鎖の入力も試してみる。などとするのが良い。

落下処理も同様に、サンプルと異なる、より簡単な入力を利用してためしてみるのが良い。

連鎖があり、一見してどうなるかよくわからないようなサンプルであったときに、それを利用してsleep(1)しながら表の状態を出力…などという方法でデバッグするのは良い方法とは思えない。

以下は自分のコードだが、他の人に比べて長め。

int N;
int score[6];
 
void drop(vector<vector<int>>& a) {
  rep(j, 5) {
    deque<int> d;
    rep(i, 5) {
      if(a[i][j] != -1) {
        d.push_back(a[i][j]);
      }
    }
 
    int dsize = d.size();
    for(int i=4; i>=0 && !d.empty(); i--) {
      a[i][j] = d.back();
      d.pop_back();
    }
    rep(i, 5-dsize) {
      a[i][j] = -1;
    }
  }
}
 
int dist(vector<vector<int>> const& a, int num, int i, int j, int dy, int dx, int sum = 0) {
  i += dy, j += dx;
  if(!in_range(i, j, 5, 5)) return sum;
  if(a[i][j] != num) return sum;
  return dist(a, num, i, j, dy, dx, sum + 1);
}
 
int simulate(vector<vector<int>>& a) {
  int ret = 0;
  int bonus = 1;
 
  while(1) {
    set<int> used;
    rep(i, 5) rep(j, 5) {
      if(a[i][j] == -1) continue;
      int movel = dist(a, a[i][j], i, j, 0, -1);
      int mover = dist(a, a[i][j], i, j, 0, +1);
      int movet = dist(a, a[i][j], i, j, -1, 0);
      int moveb = dist(a, a[i][j], i, j, +1, 0);
      if(mover - movel + 1 >= 3) {
        REP(x, j - movel, j + mover + 1) {
          assert(a[i][x] != -1);
          assert(a[i][x] == a[i][j]);
          used.insert(i*5+x);
        }
      }
      if(moveb - movet + 1 >= 3) {
        REP(y, i - movet, i + moveb + 1) {
          assert(a[y][j] != -1);
          assert(a[y][j] == a[i][j]);
          used.insert(y*5+j);
        }
      }
    }
 
    for(auto && e: used) {
      ret += score[a[e/5][e%5]] * bonus;
      a[e/5][e%5] = -1;
    }
 
    bonus ++;
    if(!used.size()) break;
    drop(a);
  }
 
  return ret;
}
 
 
 
int dfs(vector<vector<int>> a, int y, int x, int idx = 0) {
  auto aa = a;
  int ret = simulate(a);
  if(idx < N) {
    rep(k, 4) {
      int ny = y + dy[k], nx = x + dx[k];
      if(!in_range(ny, nx, 5, 5)) continue;
      a = aa;
      swap(a[y][x], a[ny][nx]);
      maximize(ret, dfs(a, ny, nx, idx + 1));
    }
  }
  return ret;
}
 
int solve(vector<vector<int>>& a) {
  int ret = 0;
  rep(i, 5) rep(j, 5)  {
    maximize(ret, dfs(a, i, j));
  }
  return ret;
}
 
int main() {
 
  for(; cin >> N && N >= 0;) {
    vector<vector<int>> a(5, vector<int>(5));
    rep(i, 5) rep(j, 5) cin >> a[i][j];
    rep(i, 5) cin >> score[i+1];
    cout << solve(a) << endl;
  }
   
  return 0;
}