POH7「プログラミングで彼女をつくる」「めがね」ゲットチャレンジ!
POH8の問題を全部解いてしまったので、昔のにも挑戦してみます。
問題
(適当に省略しています。)
あなたはクライアントから画像分析の仕事を受けました。
N × N ピクセルの白黒画像と M × M ピクセルの白黒画像が与えられます。 白黒画像の各画素は 0 または 1 のいずれかです。 N × N ピクセルの画像を入力、M × M ピクセルの画像をパターンと呼ぶことにします。
あなたの仕事は、入力からパターンとの完全一致を探すことです。
入力とパターンがピクセルの位置 (y, x) で完全一致するとは、 全ての i, j (i = 0, 1, ... M - 1, j = 0, 1, ... M - 1) について、 (入力の位置 (y + j, x + i) におけるピクセル) = (パターンの位置 (j, i) におけるピクセル) が成立することをいいます。
また、依頼主からは、入力にはパターンと完全一致する箇所は必ず 1 つだけ存在するということを 伝えられています。
条件
すべてのテストケースにおいて、以下の条件をみたします。
10 ≦ N ≦ 100, 2 ≦ M ≦ 10
q_{i, j}, p_{i, j} は 0 または 1
パターンと完全一致する箇所は必ず1つだけ存在します
入力例1
入力
4
0 0 1 0
0 1 1 0
0 1 0 1
1 1 1 0
3
0 1 1
0 1 0
1 1 1出力
1 0
今回は範囲が狭いため(高々1万個)普通に探せば問題なさそうです。
さらに、一致するかどうかもいったん文字列化すると簡単に比較できるのでよいでしょう。