square869120Contest #3: B - 石落としゲーム

問題

B - 石落としゲーム / Falling Stone Game

解説

簡易版のぷよぷよのようなもの。言われたとおりにシミュレーションするしかない。よくある問題。

基本のグリッドを vector<string> で持ったのに対して、各列について落とす処理ために消したブロック以外を列ごとに一度stackに詰めた。詰めたブロックを、再度列ごと下から埋め直せば良い。

落とす問題はグリッド上で一度に処理せずにstack, vectorなどのデータ構造に詰め直したほうが楽だと思っていて、大体いつもそうしている。

また、C++で書けば計算量を対して考慮せずにざっくり実装しても間に合うため、そのように実装した。特に定数倍などはガン無視している。個人的な課題として、ざっくり実装するとミスは抑えられてもコード量が長くなるので、コーディングの時間が間延びしてしまう。

using Grid = vector<string>;

int H, W, K;
Grid v;

Grid remove_cell(Grid const& in, int y, int x) {
  auto result = in;
  result[y][x] = '-';
  return result;
}

Grid drop(Grid const& in) {
  vector<stack<char>> stks(W);
  rep(i, H) rep(j, W) {
    if (in[i][j] != '-') {
      stks[j].push(in[i][j]);
    }
  }

  Grid result(H);
  rep(i, H) result[i].resize(W, '-');
  rep(j, W) rep(i, H) {
    if (!stks[j].empty()) {
      auto cell = stks[j].top();
      stks[j].pop();
      result[H - i - 1][j] = cell;      
    } else {
      result[H - i - 1][j] = '-';
    }
  }
  return result;
}

string remove_right_forward_in_line(string const& in, int sj) {
  auto work = in;
  const auto rmchar = in[sj];
  REP(j, sj, W) {
    if (work[j] != rmchar) { break; }
    work[j] = '-';
  }
  return work;
}

Grid remove_connected_cells(Grid const& in) {
  auto work = in;
  rep(i, H) rep(j, W - K + 1) {
    if (work[i][j] == '-') { continue; }
    auto s = work[i].substr(j, K);
    s.erase(std::unique(s.begin(), s.end()), s.end());
    if (s.size() == 1) {
      work[i] = remove_right_forward_in_line(work[i], j);
    }
  }
  return work;
}

int calc_sum(Grid const& in) {
  int sum = 0;
  rep(i, H) rep(j, W) {
    sum += in[i][j] == '-' ? 0 : (in[i][j] - '0');
  }
  return sum;
}

int solve(Grid work) {
  int score = 0;
  for (int pexp = 0; ; pexp++) {
    auto next_work = drop(remove_connected_cells(work));
    auto diff = calc_sum(work) - calc_sum(next_work);
    if (diff == 0) { break; }
    score += (1 << pexp) * diff;
    work = next_work;
  }
  return score;
}

int solve() {
  int max_score = 0;
  rep(i, H) rep(j, W) {
    maximize(max_score, solve(drop(remove_cell(v, i, j))));
  }
  return max_score;
}

int main() {
  cin >> H >> W >> K;
  v.resize(H); cin >> v;
  cout << solve() << "\n";
}