SRM 530 DIV1 Easy - GogoXCake （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11274&rd=14723
ケーキをカットする問題。
カットされたあとのケーキの形と、カットするナイフが与えられる。
ナイフを当てるときは必ず、そのマスにもケーキがなければいけない。
カット後のケーキの形にすることができればＹｅｓ，ダメならＮｏを返す。
解き方
単純にシミュレーションするだけ。
カットできるときはカットしなければ答えを導けないことがわかれば、単純に実装できる。
最初にカットするべきマスとダメなマスをマーキング。
次に順番にナイフを当てていき、全てカットすることができるときだけカットする。
最後にカットするべきマスが残っていればＮｏ，残っていなければＹｅｓ．
コード
class GogoXCake {
public: string solve(vector<string> cake, vector<string> cutter) {
int h=cake.size(),w=cake[0].size();
int ch=cutter.size(),cw=cutter[0].size();
int g[h][w];
FORE(i,0,h)FORE(j,0,w){
if(cake[i][j]=='.')g[i][j]=-1;
else g[i][j]=1;
}
FORE(i,0,h-ch+1){
FORE(j,0,w-cw+1){
int invalid=0;
FORE(a,i,ch+i)FORE(b,j,cw+j)if(cutter[a-i][b-j]=='.'&&g[a][b]!=-1)invalid=1;
if(invalid)continue;
FORE(a,i,ch+i)FORE(b,j,cw+j)if(cutter[a-i][b-j]=='.')g[a][b]=1;
}
}
FORE(i,0,h)FORE(j,0,w)if(g[i][j]==-1)return "NO";
return "YES";
}
};
public: string solve(vector<string> cake, vector<string> cutter) {
int h=cake.size(),w=cake[0].size();
int ch=cutter.size(),cw=cutter[0].size();
int g[h][w];
FORE(i,0,h)FORE(j,0,w){
if(cake[i][j]=='.')g[i][j]=-1;
else g[i][j]=1;
}
FORE(i,0,h-ch+1){
FORE(j,0,w-cw+1){
int invalid=0;
FORE(a,i,ch+i)FORE(b,j,cw+j)if(cutter[a-i][b-j]=='.'&&g[a][b]!=-1)invalid=1;
if(invalid)continue;
FORE(a,i,ch+i)FORE(b,j,cw+j)if(cutter[a-i][b-j]=='.')g[a][b]=1;
}
}
FORE(i,0,h)FORE(j,0,w)if(g[i][j]==-1)return "NO";
return "YES";
}
};
