0

我从两天以来一直在考虑这个问题，但没有找到可行的解决方案：

我有一个二维数组，想要找到最大数量的连接项目（水平和垂直，而不是对角线），但该组中的任何项目都不应该重复。

可能组的示例：

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

这是我的问题的简化视图，因为在“现实”中，数组是 6x9，并且存在三种不同类型的“元素”（比如说数字、字母和符号），每 30 个不同的可能项目和一个空白 (-) 元素。在第一遍中，我检查每个位置并找到相同元素的所有连接项。这使用递归函数相对容易实现，字段 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:0，这将导致最多 4 个连接的不同项目，因为如果不触摸已经在组中的项目（这里是另一个 C），您将无法到达另一个项目。

对于我的问题，检测最大值就足够了。10 个项目组中有 6 个不同的连接项目。

上述示例的可能组是（当我检查位置 2:1 “F”时）：

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

我没有找到可以做到这一点的算法，比如我用来查找数组中相同元素的所有项目的简单递归函数。它似乎要复杂得多。

例如，算法还必须认识到它不会将位置 3:4 的 E 添加到组中，而是将位置 2:3 的 E 添加到组中。

我认为上述中间步骤首先找到一个元素的所有连接项是不必要的，但目前我在这里和我的代码中这样做是为了让事情更清楚:)

4

2 回答 2

0

Because all algorithm I tried don't work or would use a big recursive stacks I have done it another way:

For my purpose it is enough to check for max. 5 connected different items in a group of elements. I made masks (around 60) for all possible combinations for 5 items. Here five examples.

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

Now I check each connected component with these masks. If all five items on this positions are different the check is true. The actual start position for the check in the mask is always in one of the four corners.

This way it takes less memory and less calculations than every algorithm I tried, but this resolution would be not acceptable for more than six or seven items because there would be to many masks.

于 2013-02-22T11:49:55.663 回答
0

这是一个DFS问题。算法应该是；

对于每个连接的组件，dfs以 a开头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 回答