出个题目:输入一个二维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)级别的算法。
最好还是动手写一写,看你能多长时间写出来?用自己最熟悉的语言。
------解决方案--------------------------------------------------------
来学习下
class Program
{
static List<List<Point>> list = new List<List<Point>>();
static List<Point> close = new List<Point>(); //处理过的点放入close集合,不再访问
static bool[,] B = new bool[100, 40];
static int listCount = 0;
static void Main(string[] args)
{
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;
}
}
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 40; j++) //循环扫描每个点,发现一个点为true时,停止循环,并以该点为基地,
{ //广度优先搜索所有可以到达的点
if (B[i, j] && !close.Contains(new Point(i, j)))
{
Finder(i, j, listCount++);
close.Add(new Point(i, j));