本問(shift のみ): ABC307C
類題(回転あり): ABC322D
解法
置き方を全探索したいが，少し減らす必要がある． 何も考えずに置くと， A, B, X それぞれについて \(30^2\) 通り調べるので， \(30^6 = 729,000,000\) となって厳しい． 考えてみれば，\(A\) は固定してよいので， \(B,X\) だけ動かせばよい．
実装
Grid の問題の実装例
- Vector
- 座標の set を保持
- bitset で場所を保持
等がある． 今回は，座標の set を保持する方針で行う． この方法は，負の数の座標が出ても問題が無いので実装が楽． また，不要な座標は持たないので，vector に比べてメモリと実行時間が 節約できる． 実際，この方法なら \(X\)の置き方を調べるときに， \(C\) における '#' の座標の個数しか調べなくてよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename T, const T inf>
struct Grid{
set<pair<T,T>> p;
Grid(){}
rep(r, s.size()){
rep(c, s[r].size())
if(s[r][c] == '#') p.insert({r,c});
}
}
Grid<T,inf> shift(T dr, T dc) const {
Grid<T,inf> ret;
for(auto [r,c]: p){
ret.p.insert({r + dr, c + dc});
}
return ret;
}
Grid<T,inf> merge(const Grid<T,inf> a) const {
Grid<T,inf> ret = *this;
for(auto rc: a.p) ret.p.insert(rc);
return ret;
}
// inf is the infinity
pair<T,T> corner() const {
pair<T,T> ret = {inf, inf};
for(auto rc: p){
chmin(ret, rc);
}
return ret;
}
Grid<T,inf> adjust() const {
if(p.size() == 0) return Grid<T,inf>();
pair<T,T> co = corner();
return shift(-co.first, -co.second);
}
Grid<T,inf> rotate() const {
Grid<T,inf> ret;
for(auto [r,c]: p){
ret.p.insert({-c,r});
}
ret = ret.adjust();
return ret;
}
bool include(const Grid<T,inf> a) const {
for(auto [r,c]: a.p){
if(p.find({r,c}) == p.end()) return false;
}
return true;
}
bool operator == (const Grid<T,inf> a) const {
return p == a.p;
}
void show(){
for(auto [r,c]: p){
cout << r << " " << c << endl;
}
cout << endl;
}
};
int main() {
using G = Grid<ll,(ll)1e18>;
rep(i,3){
ll h,w; cin >> h >> w;
cinv(s);
sh[i] = G(s);
}
sh[2] = sh[2].adjust();
srep(r1, -25, 26) srep(c1, -25, 26){
G g;
g = g.merge(sh[0]);
g = g.merge(sh[1].shift(r1,c1));
g = g.adjust();
if(g == sh[2]) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
