atcoder abc218 C - Shapes

問題

C - Shapes

解法

# か . どちらかの情報がわかれば図形は作れるので、今回は # の座標集合だけを持つようにして考える。

図形の変形は以下のように考える。

• 平行移動は最も左にある座標を選び、それを原点に移動させる形で全体移動させて合わせる。
• 90度回転は (x, y) -> (-y, x) で変形可能

Tの方を原点移動後に固定して、Sを360度回転分試して一致したらYes, 一致できなかったらNoとすれば良い。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using P = pair<int,int>;

void move_to_origin(vector<P> &p) {
  sort(p.begin(), p.end());
  auto [a,b] = p[0];
  for (auto &v: p) v = { v.first-a, v.second-b };
  return;
}

void solve(vector<P> sp, vector<P> tp) {
  // 原点に平行移動
  move_to_origin(sp);
  move_to_origin(tp);

  REP(i,4) {
    // 一致したら終了
    if (sp == tp) { cout << "Yes" << endl; return; }

    // 90度回転させる
    for (auto &v: sp) v = { -v.second, v.first };
    move_to_origin(sp);
  }

  cout << "No" << endl;
  return;
}

int main() {
  int n; cin >> n;

  vector<P> sp,tp;
  REP(i,n) REP(j,n) {
    char c; cin >> c;
    if (c == '#') sp.emplace_back(P{i,j});
  }
  REP(i,n) REP(j,n) {
    char c; cin >> c;
    if (c == '#') tp.emplace_back(P{i,j});
  }

  solve(sp,tp);
  return 0;
}

雑感

平行移動が出てきたら、原点に移動させる。 D問題の方が難しく思えたけど、C問題の方がdiff高かったのは意外。