大きい図形で簡単な図を検索

Question

大きな図形が四角で構成されています。 また、私はの単純な数字も四角で構成されています。

の単純な数字はの大きな数字にありますか？

- ありがとうございました。

Answer 1

あなたは正方形のグリッド上に配置されていると述べているので、あなたは、対応する四角形が等しいかどうかを確認するために、各小図でグリッドをループするだけで試みることができます。そうであれば、簡単な図形のインスタンスが1つ見つかります。

好きな人は、単純な図形を交差しないパスとしてエンコードすることができます。つまり、最初の単純図形は、開始から右に移動するようなパスになります。次に、大きな図形の各四角形について、パスを完了して大きな図形の四角形にとどめることができれば、単一の図形のインスタンスが見つかりました。

Answer 2

ビッグフィギュアの各行Bがパックされたビットの配列で表され、最大の小さな図形がh行v列のグリッド内に含まれると仮定します。 h * vビット（または4 * 2、または4 * 4、または8 * 2など）を使用して、便利なサイズにすることができます（h = 3、v =各小さな図形sに対してマスクM_sを作る。それぞれの（x、y）において、Bで設定され現在のウィンドウ内にあるビットを表す値M（x、y）を形成する、h行v列の「ウィンドウ」を上下に動かす。この値は、（すなわち、を徐々に計算することができます。M_s & M(x,y) == M_sの場合は、小さな数字の出現が見つかりました。

注、上記の方法は、小さな図の空白のセルは「ドントケア」であることを想定し、そのような細胞はない「ドン」であればすなわちはBに空白または非ブランクのいずれかを一致させることができます以前に使用された非ブランクのマップの他に、それぞれの小さな図形に対して、ブランクの補完的なマップが必要です。このマップはM（x、y）の補数に対してテストします。 M（x、y）ウィンドウが小さいフィギュアと同じサイズの場合、M_s & M(x,y) == M_sの代わりにテストを一緒に組み合わせてM_s^M(x,y) == 0をテストすることは可能です。

Bが非常に大きく、まばらである場合、BのビットをM（x、y）の値にするのではなく、小数のパターンをシフトしてBの単語に対して直接テストする方が高速かもしれません。シフトされた小さなパターンの配列をあらかじめ計算することができます。

小さい数字の数が多い場合は、小さな数字uがwに含まれている場合、uが見つからない場合はwのテストをスキップできます。同様に、uとvの両方がwに含まれている場合は、uまたはvのいずれかが見つからない場合はwのテストをスキップできます。ただし、このような最適化と前のような最適化は、最初の段落で説明した基本的な方法が遅すぎる場合にのみ試行してください。