Official

B - Same Map in the RPG World Editorial by en_translator


This problem asks to determine if there is a pair of non-negative integers \((s, t)\) Checking all non-negative integers for the conditions is impossible, so we first narrow down the candidate pairs of \((s, t)\).
Then we can see that we only have to consider \(s\) between \(0\) (inclusive) and \(H\) (exclusive). Because, as the height of \(A\) is \(H\), “the grid resulting from applying a vertical shift \(s\) times” and “the grid resulting from applying a vertical shift \(s + H\) times” are equal.
Similarly, we only have to consider \(t\) between \(0\) (inclusive) and \(W\) (exclusive). Thus, we now have only \(HW\) candidates of \((s, t)\).

(In the explanation below, we use 0-based indexing for \(A\) and \(B\). That is, the top-left cell is \(A[0][0]\) and the bottom-right is \(A[H-1][W-1]\).)
For a fixed \((s, t)\), how can we determine if the resulting \(A\) and \(B\) coincide? Shifting \(A\) vertically \(s\) times and horizontally \(t\) times, \(A[i][j]\) results in \(A[(i - s) \bmod H][(j - t) \bmod W]\) (where \(\bmod\) is the modulo operation). Thus, it is sufficient to check if \(A[(i - s) \bmod H][(j - t) \bmod W]\) equals \(B[i][j]\) for all points \((i, j)\).
This algorithm has \(4\)-ple loop of \(s, t, i, j\), so it has a complexity of \(\mathrm{O}(H^2 W^2)\), which is fast enough.

Sample code (C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> A(H), B(H);
  for (auto& x : A) cin >> x;
  for (auto& x : B) cin >> x;
  for (int s = 0; s < H; s++) {
    for (int t = 0; t < W; t++) {
      int ok = 1;
      for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
          if (A[(i - s + H) % H][(j - t + W) % W] != B[i][j]) ok = 0;
        }
      }
      if (ok) {
        cout << "Yes" << endl;
        exit(0);
      }
    }
  }
  cout << "No" << endl;
}

posted:
last update: