読者です 読者をやめる 読者になる 読者になる

SRM 605 Div2 Medium AlienAndGame

問題

SRM 605 - TopCoder Wiki

2次元配列の各セルが黒白で塗られている. 今任意の行のセルの色を反転できる時, 作ることの出来る最大の白色の正方形の面積を求める問題.

解答

まずの正方形を作るという作業は,操作で反転できるので特に意味は無い.

正解となる正方形を考える,位置,正方形の辺の長さを考えると作れる正方形は高々503. うん,それほど多くない.

今可能な操作は行毎の黒白反転なので, 各正方形について,各行が同じ色であれば,全て白の正方形を作ることが出来る.

全探索!

class AlienAndGame
{
public:
  int getNumber(vector <string> board)
    {
      int i, j, k;
      int n = board.size();
      int m = board[0].size();
      for (k = min(n, m); k > 1; k--){
        for (i = 0; i < n-k+1; i++){
          for(j = 0; j< m-k+1; j++){
            bool square = true;
            for(int di = 0; di < k; di++){
              bool allsame = true;
              for(int dj = 0; dj < k; dj++) if (board[i+di][j+dj] != board[i+di][j]){
                  allsame = false;
                  break;
                }
              if (!allsame) {
                square = false;
                break;
              }
            }
            if (square) return k * k;
          }
        }
      }
      return 1;
    }
};