SRM 530 Div2 Medium GogoXCake

問題

長方形のケーキと,ケーキカッターが与えられる.ケーキカッターは長方形のグリッドの内ケーキを取り除ける部分と取り除けない部分が設定されている.与えられたケーキカッターで,入力のケーキが作れるかどうかを判定する.

解答

いろいろな切り方を考えていたが,結局のところ一意な切り方しかないということに気づいた.
順番上から下,左から右にケーキを読んでいって,ある時点でケーキカッターでケーキを切れる時,もしその時点で切らなければ二度と同じように切れない.同じケーキカッターで切り続けるので.
なのでケーキを順番に読んでいって,切れる時は必ず切るようにする.そのように切っていって,もし入力のケーキのようになっていたら"YES", そうでなかったら"NO"を返す

class GogoXCake
{
public:
  vector<vector<bool> > cut;
  int n, m, cn, cm;

  string solve(vector <string> cake, vector <string> cutter)
    {
      n = cake.size();
      m = cake[0].size();
      cn = cutter.size();
      cm = cutter[0].size();
      vector<vector<bool> > board(n, vector<bool>(m, false));
      int i, j, ci, cj;
      for(i = 0; i < cn; i++){
        vector<bool> tmp;
        for(j = 0; j < cm; j++)
          if(cutter[i][j] == '.') tmp.push_back(true);
          else tmp.push_back(false);
        cut.push_back(tmp);
      }
      for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
          if(cake[i][j] == '.') board[i][j] = true;
        }
      }
      for(i = 0; i < (n - cn + 1); i++){
        for(j = 0; j < (m - cm + 1); j++){
          bool canput = true;
          for(ci = 0; ci < cn; ci++){
            for(cj = 0; cj < cm; cj++){
              if (!(!cut[ci][cj] || board[ci+i][cj+j])){
                canput = false;
                break;
              }
            }
          }
          if (canput){
            for(ci = 0; ci < cn; ci++){
              for(cj = 0; cj < cm; cj++){
                if (cut[ci][cj]) board[ci + i][cj + j] = false;
              }
            }
          }
        }
      }
      // cout << "Fuga" << endl;
      for(i = 0; i < n; i++){
        for(j = 0; j < m; j++)if (board[i][j]) return "NO";
      }
      return "YES";
    }
};