数学建模社区-数学中国

标题: 求助：计算同色方格最大数之算法 [打印本页]
作者: mikezang    时间: 2011-2-22 13:50
标题: 求助：计算同色方格最大数之算法
本帖最后由 mikezang 于 2011-2-22 14:58 编辑 + j4 W6 k2 U( A+ g

) ^4 r9 E4 K1 @$ d1 I想求教各位专家一个算法，希望能得到帮助。有如下所示方阵，大小可变，颜色数３－８，有没有一个算法可以得出各个颜色相连最大数？下图的正确结果应该是：
2 W" U: V  ?8 Z; v5 J６　２　５　１　* ^4 i) ^1 @, {  V! r+ E$ ]* C

% [7 ^4 f! i2 |- F$ W& R, b- C+ u' A) U" p; L) H& ~' b1 R3 e9 D6 k
作者: aqua2001    时间: 2011-2-22 15:59
稍加改动就是一个图。方阵中每个方块可看成一个顶点，若方阵中同色方块相邻，则该两顶点以边相连。对每种颜色都搜索最大连通分支即可。
作者: mikezang    时间: 2011-2-23 23:09
谢谢老兄的指点，根据你的意见，查到了Tarjan's Theory, 找到了Tarjan的算法，并获得了所需的结果，真是听君一句话，胜读廿年书。- m  k) D0 Y9 z
) _/ J( E7 V" A# M2 O8 b  X
再想请教一下，如果要把上图通过旋转部分方格，最终使相同颜色全部连成块，关于这个算法应该读那些方面内容？最好给出英文术语，多谢。
作者: mikezang    时间: 2011-2-23 23:10
谢谢老兄的指点，根据你的意见，查到了Tarjan's Theory, 找到了Tarjan的算法，并获得了所需的结果，真是听君一句话，胜读廿年书。
! W: Y5 o8 `3 f" y) J; M3 \2 p1 e0 {, ?2 T0 R7 x: H
再想请教一下，如果要把上图通过旋转部分方格，最终使相同颜色全部连成块，关于这个算法应该读那些方面内容？最好给出英文术语，多谢。



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5