0

私はこの問題について2日間考えていましたが、実用的な解決策が見つかりませんでした:

私は2次元配列を持っていて、接続されているアイテムの最大数(水平と垂直、対角線ではありません)を見つけたいと思っていますが、このグループのアイテムは重複してはいけません。

考えられるグループの例:

--FG- or -F--- or -----
--E--    -E---    ---AF
-BC--    CBD--    ----B
-AD--    -A---    --CDE

これは私の問題を簡略化したものです。これは、「現実」では配列が 6x9 であり、30 の異なる可能な項目と空白 (-) 要素を持つ 3 つの異なるタイプの「要素」(数字、文字、記号など) があるためです。最初のパスでは、各位置をチェックし、同じ要素の接続されたすべてのアイテムを見つけます。これは、再帰関数を使用すると比較的簡単に実現できます。フィールド 0,0 は左下にあります (別の単純化されたビュー)。

12AB-1-     The check for    -AB----  
23CD23-     position 2:0     -CD----
2*CE55-     ("C") would      --CE---
#2E2*AA     result in        --E----
#$A23BC     this:            --A----
$$F1+*E                      --F----
21C31*2                      --C----

位置 2:0 "C" のチェックは、10 個の接続された "文字" 項目を持つ配列になります。ここで、この新しい配列内で異なる最大数の接続されたアイテムを検索するため、新しいグループ内の 2 つの重複アイテムではありません。位置 2:0 の場合、グループ内に既に存在するアイテム (ここでは別の C) に触れずに別のアイテムに到達することはできないため、これは最大 4 つの接続された個別のアイテムになります。

私の問題では、最大を検出するだけで十分です。10 アイテム グループの 6 つの異なる接続アイテム。

上記の例の考えられるグループは次のようになります (位置 2:1 "F" を確認した場合):

--B----
--D----
--C----
--E----
--A----
--F----
-------

配列内の同じ要素のすべての項目を見つけるために使用する単純な再帰関数のように、それを行うアルゴリズムは見つかりません。はるかに複雑なようです。

たとえば、アルゴリズムは、3:4 の位置にある E をグループに追加するのではなく、2:3 の位置にある E をグループに追加することも認識しなければなりません。

要素のすべての接続されたアイテムを最初に見つけるための上記の中間ステップは不要だと思いますが、現時点では、物事をより明確にするためにこことコードでこれを行っています:)

4

2 に答える 2

0

これはDFS問題です。アルゴリズムは次のようになります。

接続されているコンポーネントごとに、で開始dfsしmapます。これが擬似コードです：

 void dfs(position pos, map<char, bool> m, int number) {

    //if the element is seen before, quit 
    if(m[array2d[pos] == true)
        return;

    //it is seen now
    m[array2d[pos]] = true;

    //update max value
    maxValue = max(maxValue, number);

    //go to each neighbor
    foreach(neighbor of pos) {
         dfs(neighbor, m, number+1); 
    }

    //unlock the position
    m[array2d[pos]] = false;
 }

dfs配列内の各場所から開始する必要があると思います。

于 2013-02-18T12:57:18.220 に答える
0

私が試したすべてのアルゴリズムが機能しないか、大きな再帰スタックを使用するため、別の方法で実行しました。

私の目的では、最大値をチェックするだけで十分です。要素のグループ内の5つの接続された異なるアイテム。5つのアイテムのすべての可能な組み合わせに対してマスク（約60）を作成しました。ここに5つの例があります。

----- ----- ----- ----- *----
----- ----- ----- ----- *----
----- ----- ----- ***-- ***--
----- ---*- --*-- *---- -----
***** ****- ****- *---- -----

次に、これらのマスクを使用して、接続されている各コンポーネントを確認します。この位置の5つの項目すべてが異なる場合、チェックは真です。マスクのチェックインの実際の開始位置は、常に4つのコーナーのいずれかにあります。

このように、私が試したすべてのアルゴリズムよりも少ないメモリと少ない計算で済みますが、多くのマスクが存在するため、この解像度は6つまたは7つを超えるアイテムには受け入れられません。

于 2013-02-22T11:49:55.663 に答える