出个题目：输入一个二维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)级别的算法。
最好还是动手写一写，看你能多长时间写出来?用自己最熟悉的语言。
------解决方案--------------------------------------------------------
来学习下
- C# code
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)); } } } Console.WriteLine(list.Count); } static void Finder(int i, int j, int c) { list.Add(new List<Point>()); List<Point> queue = new List<Point>(); queue.Add(new Point(i, j)); while (queue.Count != 0) { Point current = queue[0]; if (current == null) { break; } queue.RemoveAt(0); //可以到达的点 Point[] reach = new Point[8] { new Point(current.X - 1, current.Y - 1), new Point(current.X, current.Y - 1), new Point(current.X + 1, current.Y - 1), new Point(current.X - 1, current.Y), new Point(current.X + 1, current.Y), new Point(current.X - 1, current.Y + 1), new Point(current.X, current.Y + 1), new Point(current.X + 1, current.Y + 1) }; for (int k = 0; k < 8; k++) { if (reach[k].X >= 0 && reach[k].X < 100 && reach[k].Y >= 0 && reach[k].Y < 40)//没有超出范围 { if (B[reach[k].X, reach[k].Y] && !close.Contains(new Point(reach[k].X, reach[k].Y))) { list[c].Add(new Point(reach[k].X, reach[k].Y)); queue.Add(new Point(reach[k].X, reach[k].Y)); close.Add(new Point(reach[k].X, reach[k].Y)); } } } } } }
------解决方案--------------------------------------------------------
在这个帖子里混点分，不去那个帖子抢了，抢不过。
- C# code
using System.Collections.Generic;namespace CSharpTest{ class Program { struct Point { public int X; public int Y; public Point(int x, int y) { X = x; Y = y; } } class Graph { public readonly int Width; public readonly int Height; public bool[,] BitMap; public List<List<Point>> Fill() { bool[,] history = new bool[Width, Height]; List<List<Point>> result = new List<List<Point>>(); for (int i = 0; i < Width; i++) { for (int j = 0; j < Height; j++) { if (BitMap[i, j] && !history[i, j]) result.Add(BFS(i, j, history)); } } return result; } private List<Point> BFS(int x, int y, bool[,] history) { List<Point> currentPoints = new List<Point>(); Queue<Point> queue = new Queue<Point>(); Point cPoint = new Point(x, y); queue.Enqueue(cPoint); while (queue.Count > 0) { Point current = queue.Dequeue(); currentPoints.Add(current); history[current.X, current.Y] = true; for (int i = current.X - 1; i <= current.X + 1; i++) { for (int j = current.Y - 1; j <= current.Y + 1; j++) { if (i == current.X && j == current.Y) continue; if (Check(i, j) && !history[i,j]) queue.Enqueue(new Point(i, j)); } } } return currentPoints; } private bool Check(int x, int y) { if (x < 0 || x >= Width || y < 0 || y >= Height) return false; return BitMap[x, y]; } public Graph(int width, int height) { Width = width; Height = height; BitMap = new bool[width, height]; } } public static void Main() { Graph g = new Graph(4, 4); g.BitMap[0, 0] = true; g.BitMap[0, 1] = true; g.BitMap[0, 2] = true; g.BitMap[3, 1] = true; g.BitMap[3, 2] = true; g.BitMap[3, 3] = true; List<List<Point>> points = g.Fill(); } }}