8

次の ASCII アート画像を見つけるアルゴリズムはありますか?

    +
    +
   +++
 +++++++
 ++   ++
++  +  ++
++ +++ ++
++  +  ++
 ++   ++
 +++++++
   +++

次の本文の中にありますか?

complete_file_here

              + +    +              ++           +       +++    +     +
 +  ++     +   + ++++    + +       +         +          +  +   +++     +++ +
     +            + +   ++      ++  ++    + ++       +     +      +  +   +
+   ++      +  ++       +          + +       ++        ++  +           +
 ++++++ + +    +   ++  +  +   +   +  ++      +         +                     +
  + +   +      +               +      ++     +  ++            +   +    + +
+++   + ++   +  +            +  +++       + +       ++                     +
  +++++  +      +                            +  + +            +   +  +
 +   +   +              +    +      +            +  +   +      +    +     +
 ++    +              +     +       ++   +          +       +           ++

完全な形状に対応する ASCII アート イメージを黄色で強調表示する必要があります。添付の写真を参照してください。

ここに画像の説明を入力してください

大まかな形状を含むファイルを検索する必要がありますが、完全ではなく、いくつか+が欠落している可能性があります)。+形状の欠落の許容範囲は手動で設定する必要があります。

これで、データ配列 [100][100] と SlimeTorpedo 配列 [13][11] の 2 つの 2D 配列があります。

@kjartan が述べたように検出を行う方法のコード (3-4 箇条書き):

int match = 0;
for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
        //Compare DataArr[i][j] with SlimeTorpedoArr[i][j]
        //Look for "checked" position in the picture ("+"), 
        //which corresponds to a checked position in the 
        //slime torpedo array.
        //match++;
    }
}

この問題にアプローチするための一般的なガイダンスは何ですか?

4

3 に答える 3

4

マッチスコアでブルートフォースを試してください：

  • 「スライム魚雷」の周りに「正方形」を定義します。これは、幅と高さが魚雷より少し広くて高い 2D 配列です。
  • その 2D 配列で、目的のイメージを作成するために必要に応じて、セルをチェック済みまたはチェックなしとしてマークします。
  • 次に、画像全体の各文字 (これを「インデックス」位置と呼びましょう) をループし、それぞれについて、その近くの位置を 2D 配列内の対応する文字の位置と比較します。
  • スライム魚雷配列のチェックされた (またはチェックされていない) 位置に対応する、画像内の「チェックされた」(またはチェックされていない) 位置を探します (たとえば、画像内の現在のインデックス位置の上に文字 X があり、左に Y がある場合、スライム魚雷アレイの中心点の上方 X と左側 Y のステータスに一致します)。そのような「一致」ごとに、画像内のそのインデックス位置に 1 つの「ポイント」を追加します。

ここに秘訣があります。これをより効果的にするには、スライム魚雷のいくつかの位置だけをチェックします。これにより、大まかに言えば、実行時間が 10 分の 1 に短縮されます。

つまり、画像全体の各文字に対して(1/10)*をチェックする必要があります。the number of characters in the 2D array

全体像で最高得点の位置を追跡します。最高得点の位置がベストマッチとなります。

必要に応じて、さまざまな詳細度でこれを複数回実行できます。たとえば、最初は位置の 1/20 のみをチェックし、次に 1/2、次に 1/2 をチェックしますが、今回はたとえば最高の 20 のみに焦点を当てます。 （または50？100？）最初のラウンドからの得点位置。

(別の方法として、あるしきい値 S より高いスコアを付けたすべての位置をより詳細にスキャンすることもできます)。

興味深い質問です。:)

以下のコメントに応じて更新します。

私の説明が少しわかりにくかったかもしれません。要するに/疑似コードでは、各セルのスコアを見つけるために次のようなことをする必要があります:

foreach(DataArraRow dataRow in dataArray){
    foreach(IndexCell index in dataRow){        

        // initialy, no score for this cell in the data array:
        indexCell.score = 0;

        // Now iterate through all SlimeTorpedo cells, and compare the 
        // symbol in it to the corresponding symbol in te data array:
        foreach(SlimeArrayRow slimeRow in slimeTorpedoArray){
            foreach(SlimeTorpedoCell slimeCell in slimeRow){
                if(IsMatchingSymbol(slimeCell.xPosition, 
                                    slimeCell.yPosition, 
                                    slimeCell.symbol, 
                                    indexCell){
                    indexCell.score += 1;
                }else{
                    indexCell.score -= 1;
                }
            }              
        }

    }
}


Function IsMatchingSymbol(x, y, slimeSymbol, indexCell){
   // Find the cell in the data array corresponding to the 
   // "slimeCell" currently being checked:
   var cellToCheck = getCell(indexCell.xPosition + x, 
                             indexCell.yPosition + y);

   if(cellToCheck.symbol == slimeSymbol){
       return true;
   }else{
       return false;
   }

}

これは明らかに少し面倒で、すべての詳細についてはわかりませんが、機能するはずの一般的なアイデアを示していることを願っています. これを反復し終わったら、すべてのセルを再度反復し、最高スコアのセルを選択します (または、途中で別のハイスコア リストを作成します。おそらくそのほうが速いでしょう)。

ForEachループを通常のループなどに置き換えるなど、いくつかの変更を行う必要がFor(int i=0; i < someArrayLength; i = i + levelOfDetail){ ... }ありlevelOfDetailます。私はあなたがそれを解決できると確信しています... ;)

于 2013-01-09T21:30:20.353 に答える
4

最初の形状の幅と高さのパラメーター (文字数) がわかっているとします。widthそれらを ととしましょうheight。

  • 入力をビット (または + 記号) の 2D 配列にエンコードします。したがって int[][] inputBits = new int[height][width];、正しく入力する必要があります。（それはあなたの仕事です、おい。）
  • 次に、より大きな形状に単純な検索を適用します (別の 2D 配列にもエンコードされていると仮定します)。ピボット領域を 1 つずつ右にシフトし (ピボット領域は最初の形状の領域に相当します)、ピボット領域 (2D 配列) のすべての要素が最初の形状に等しいかどうかを確認します。それはブルートフォースアルゴリズムです=）
于 2013-01-09T20:52:56.580 に答える
1

興味のある方のために、Java で XOR マッピングを使用してこの問題を解決しました。

https://bitbucket.org/bluegod1/blifoscope-java/

また、誤検知や重複が発生する可能性があることも考慮しており、適切な一致の最小しきい値を指定したり、カスタム データ イメージ ファイルを追加したりするオプションがあります。

于 2013-10-07T15:54:46.187 に答える