查找二维数组连接不同的元素

我在思考这个问题，因为两天，没有找到一个可行的解决：查找二维数组连接不同的元素

我有一个二维数组，并希望寻找项目的最大数量连接（水平和垂直，而不是对角线），但该组的任何项目都不应重复。用于可能的基团

实例：

--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添加到组中。

我认为上述中间步骤，首先找到全部连接项目的要素是不必要的，但此刻我这样做在这里和我的代码，以使事情更加清楚:)

来源

2013-02-18 user1043409

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

对于每个连接的组件，请使用map启动dfs。下面是一个伪代码：

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-18 12:57:18 ogzd

这适用于大多数情况，但如果有一些相同的项目，它并不总是找到所有不同的项目。我认为这与它看待邻居的顺序有关。我认为我必须用每一个可能的检查邻居的顺序来检查每个位置。如果检查失败，其他方法将返回到以前的位置。但所有这些都会以许多递归调用结束。对于我的特殊情况，我找到了另一个决议 – user1043409 2013-02-22 11:54:39

因为所有的算法我试图不工作或将使用一个大的递归栈我已经做了另一种方式：

对于我的目的就足够了检查最大。 5在一组元素中连接了不同的项目。我为5种物品的所有可能组合制作了面具（约60）。这里有五个例子。

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

现在我用这些掩码检查每个连接的组件。如果这个职位上的所有五个项目都不同，那么检查是真实的。掩码检查的实际起始位置始终位于四个角落中的一个。

这种方式比我尝试过的每种算法都需要更少的内存和更少的计算，但是这个解决方案对于超过六个或七个项目是不可接受的，因为会有很多掩码。

来源

2013-02-22 11:49:55 user1043409

查找二维数组连接不同的元素

回答

相关问题