Official
B - Spot the Difference Editorial by Nyaan
この問題は文字列処理と for 文の使い方を問うている問題です。この問題が解けなかった人は文字列の使い方を復習してみましょう。
この問題はグリッド全体を走査して \(A\) と \(B\) で異なる文字を発見することで解くことが出来ます。具体的には、次のアルゴリズムを実装するとよいです。
- \(i = 1, 2, \dots, N\) の順に次の操作を行う。
- \(j = 1, 2, \dots, N\) の順に次の操作を行う。
- \(A_{i, j}\) と\(B_{i, j}\) が同じ文字かどうか調べる。
- 同じ文字だった場合は何もしない。
- 異なる文字だった場合は \((i, j)\) を出力して全ての操作を終了する。
- \(A_{i, j}\) と\(B_{i, j}\) が同じ文字かどうか調べる。
- \(j = 1, 2, \dots, N\) の順に次の操作を行う。
計算量は \(\mathrm{O}(N^2)\) で十分高速です。
- 実装例 (C++)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<string> A(N), B(N);
for (auto& s : A) cin >> s;
for (auto& s : B) cin >> s;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] != B[i][j]) {
cout << i + 1 << " " << j + 1 << endl;
return 0;
}
}
}
}
posted:
last update: