出个题目：输入一个二维随机bool数组B[,],求出全部连通域（8连接）
出个题目：输入一个二维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));
}
}
}
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));
}
}
}
}
}
}
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();
}
}
}
