SRM530 Div1 Easy - GogoXCake
問題
GogoくんがJohnにケーキが乗った皿とケーキカッターt(どちらも長方形)を渡した
皿は最初全マスにケーキが詰まっていて、皿にカッターを乗せて押すと、t[i][j]='.'のマスからはケーキが取り除かれ、t[i][j]='X'のマスは何も起こらない
ただし
① カッターは回転したり反転したりすることは出来ない
② t[i][j]='.'の部分を既にケーキがないマスに押し当てるようなカットは禁止
③ カッターが皿からはみ出すようなカットは禁止
これらの制約は守りながら切るように伝えた
Johnが帰ったあと残ったケーキの状態sが与えられる ('X' がケーキを表し '.' が空マスを表す)
Johnがちゃんと制約を満たしてカットしたかどうか判定せよ
1 <= (皿とカッターのタテ・ヨコサイズ) <= 50
カッターの上下左右それぞれ1辺には少なくとも1つ '.' のマスが存在することが保証される
解法
逆に考えると、sのケーキマスと空マスを反転し、その皿を制約を守りながらカットし、ケーキを全て取り除ければ良いことになる
以下そういう問題として考える
sの左上から順に見ていき、ケーキがあるマスがあった場合、そのケーキを取り除くには、そこにカッターの1行目の最も左の '.' を合わせて切り取るしかない
(∵ そのマスより左上は空になっているはずだから、これ以外の '.' を合わせて切ろうとすると必ず制約②を破るため)
このような切り方をすると制約のどれかを破ってしまうならその時点で答えはNO
最終的に皿を空にできたら答えはYES
蟻本p141の例題と似てるかな
これを思い出した
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));} class GogoXCake { public: string solve(vector<string> s, vector<string> t) { int h = s.size(), w = s[0].size(), hh = t.size(), ww = t[0].size(), x = find(all(t[0]), '.') - t[0].begin(); rep(i,h) rep(j,w) if (s[i][j]=='.') rep(k,hh) rep(l,ww) if (t[k][l]=='.') { if (ool(i+k,j+l-x,h,w) || s[i+k][j+l-x]=='X') return "NO"; s[i+k][j+l-x] = 'X'; } return "YES"; } };