AOJ2299 Tiles are Colorful

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

以下のようなH*Wのグリッドがある。
..A.......
.......B..
..........
..B.......
..A.CC....
ある空のマスから上下左右4方向に初めてぶつかったアルファベットに2つの同じ文字であれば、ソレラは消去されて得点が2点得られる。同じ文字のペアが2つあれば、全て消去され、4点得られる。
同じアルファベットは0個または2個存在する。
得点を最大化せよ。

H, W <= 500

解答
同じアルファベットは0個または2個存在することに着目すると、グリッドのサイズが大きいケースにおいて空のマスがほとんどとなるので、座標を縮めることが出来る。
縮めた結果、アルファベットが隣り合わせになってしまうと、それらがペアの場合消すことが出来なくなってしまう。なので、アルファベットがあるマスに隣接する空のマスは縮めないなどとすると良い。

また、どのアルファベットのペアから消しても問題ない。同じ文字が0個か2個なので、あるペアを消してしまったら、別のペアが消せなくなるということはないからである。

以下のコードは特に座標の縮め方が汚いが修正していない。

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int H, W;

void solve(vector<string>& G) {

  int res = 0;

  while(1) {
    bool ok = 0;
    rep(i, H) rep(j, W) {
      if(G[i][j] == '.') {
        map<char, vector<pair<int, int>>> mp;
        rep(k, 4) {
          int y = i, x = j;
          while(1) {
            y += dy[k], x += dx[k]; if(!in_range(y, x, H, W)) break;
            if(G[y][x] != '.') {
              mp[G[y][x]].emplace_back(y, x);
              break;
            }
          }
        }

        for(auto && e: mp) {
          if(e.second.size() > 1) {
            G[e.second[0].first][e.second[0].second] = '.';
            G[e.second[1].first][e.second[1].second] = '.';
            res += 2;
            ok = 1;
          }
        }
      }
    }
    if(!ok) break;
  }
  cout << res << endl;
}

int main() {

  cin >> H >> W;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  rep(i, H) rep(j, W) {
    if(isalpha(G[i][j])) {
      rep(k, 4) {
        int ni = i + dy[k], nj = j + dx[k];
        if(!in_range(ni, nj, H, W)) continue;
        if(G[ni][nj] == '.') G[ni][nj] = '-';
      }
    }
  }

  int k = 0;
  rep(i, H) {
    if(G[i] != string(W, '.'))
      G[k++] = G[i];
  }
  H = k;

  vector<string> T(W); rep(i, W) T[i].resize(H);
  rep(i, W) rep(j, H) {
    T[i][j] = G[j][i];
  }

  k = 0;
  rep(i, W) {
    if(T[i] != string(H, '.'))
      T[k++] = T[i];
  }

  W = k;

  G.clear(); G.resize(H); rep(i, H) G[i] = string(W, '.');

  rep(i, H) rep(j, W)
    G[i][j] = T[j][i] == '-' ? '.' : T[j][i];

  solve(G);

  return 0;
}