毕业论文开发语言企业开发JAVA技术.NET技术WEB开发Linux/Unix数据库技术Windows平台移动平台嵌入式论文范文英语论文
您现在的位置: 毕业论文 >> 嵌入式 >> 正文

输入一个二维随机bool数组B[,],求出全部连通域

更新时间:2012-7-17:  来源:毕业论文

出个题目:输入一个二维bool数组B[,],求出全部连通域(8连接)

连通,就是格子上,8个方向上值相同,都是1.

连通域用点的集合表示,如List<Ponit>或者你自己熟悉的语言的方便的表达方式都可以。

语言不限。尽量不要用太复杂的数据结构。

输入数组大小:int x=100,int y=40
输出:List<List<Ponit>>

---------------------------------------------------------------------------------------------
这个题目很实用,在模式识别领域可以作为去噪音,切分,和判断某些形体特征之用。
也可能会作为面试题,ACM竞赛题目。

实在没时间写,或者写不出来
http:-//download.csdn-.net/source/3271097
这里有个O(n)级别的论文。
目前有O(n^3),O(n^2),O(n*lgn),O(n)级别的算法。

最好还是动手写一写,看你能多长时间写出来?用自己最熟悉的语言。

    bool[,] B = new bool[100, 40];
            Random r = new Random();
            for (int i = 0; i < 100; i++)
            {
                for (int j = 0; j < 40; j++)
                {
                    int k = r.Next(0, 2);
                    B[i, j] = k == 0;
                }
            }
            int[,] A = new int[100, 40];
            List<List<Point>> list = new List<List<Point>>();
            for (int i = 0; i < 100; i++)
            {
                for (int j = 0; j < 40; j++)
                {
                    if (B[i, j])
                    {
                        if (j > 0)//不在左边缘
                        {
                            if (i == 0)//在第一行,只需判断左面的元素
                            {
                                if (B[i, j - 1])
                                {
                                    if (A[i, j - 1] != 0)//左面有值,则此点与左点连通
                                    {
                                        A[i, j] = A[i, j - 1];
                                        list[A[i, j] - 1].Add(new Point(i, j));
                                    }
                                    else//左点没值,这是一个新的连通
                                    {
                                        A[i, j] = list.Count + 1;
                                        list.Add(new List<Point> { new Point(i, j) });
                                    }
                                }
                                else//左点没值,这是一个新的连通
                                {
                                    A[i, j] = list.Count + 1;
                                    list.Add(new List<Point> { new Point(i, j) });
                                }
                            }
                            else//不在第一行
                            {
                                if (B[i, j - 1])//先判断左点
                                {
                                    if (A[i, j - 1] != 0)//左面有值,则此点与左点连通

[1] [2] 下一页

设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©youerw.com 优尔论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。