SRM 610 Div2 Medium TheMatrix

問題

SRM 610 - TopCoder Wiki

2次元平面上に01が書かれたボードが与えられるので この中に含まれるチェスボードの最大面積を求める問題. ここでチェスボードとは隣り合うセルが自セルと違う数字のこと.

解答

  • 入力は100x100,チェスボードも100x100なので,少しうまく処理しないとTLEしそう.
  • i行目でj列から伸ばせる最大の数を前処理.これで何回も計算しなくていいようにする.
  • i行目j列から始まる横幅xの面積最大のチェスボードは,前処理した最大数がx以上となる行をグリーディーに計算すれば良い.
  • 全ての行,列,横幅を計算する100 * 100 * 100 * 100ぐらいの処理で実行可能.

うまくやれば横幅も特に決める必要がないので,100* 100 * 100ぐらいで処理できる.

class TheMatrix
{
public:
  int MaxArea(vector <string> board)
    {
      int n = board.size();
      int m = board[0].size();
      vector<vector<int> > mat(n, vector<int>(m, 1));
      int i, j, ii, jj, l;
      for (i = 0; i < n; i++){
        for (j = 0; j < m; j++){
          for (l = 1; (j + l) < m && board[i][j+l-1] != board[i][j+l]; l++);
          mat[i][j] = l;
          // cout << "mat[" << i << "][" << j << "]=" << mat[i][j] << endl;
        }
      }
      int res = 1;
      for (l = max(n, m); l >= 1; l--){
        for (i = 0; i < n; i++){
          for (j = 0; j < m; j++){
            if (mat[i][j] < l) continue;
            for (ii = i+1; ii < n && mat[ii][j] >= l && board[ii][j] != board[ii-1][j]; ii++); 
            res = max(res, (ii - i ) * l);
          }
        }
      }
      return res;
    }
};