出个题目：输入一个二维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)级别的算法。最好还是动手写一写，看你能多长时间写出来?用自己最熟悉的语言。
输出：List<List<Ponit>>---------------------------------------------------------------------------------------------
这个题目很实用，在模式识别领域可以作为去噪音，切分，和判断某些形体特征之用。
也可能会作为面试题，ACM竞赛题目。实在没时间写，或者写不出来
http://download.csdn.net/source/3271097
这里有个O(n)级别的论文。
目前有O(n^3),O(n^2),O(n*lgn),O(n)级别的算法。最好还是动手写一写，看你能多长时间写出来?用自己最熟悉的语言。
也就是0(m*n)的啊！用BFS搜索一遍就可以了！
acm里的确好多这样的问题！
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)//左面有值，则此点与左点连通
{
A[i, j] = A[i, j - 1];
list[A[i, j] - 1].Add(new Point(i, j));
}
}
else if (B[i - 1, j - 1])//判断左上
{
if (A[i - 1, j - 1] != 0)//左上面有值，则此点与左上点连通
{
A[i, j] = A[i - 1, j - 1];
list[A[i, j] - 1].Add(new Point(i, j));
}
}
else if (B[i - 1, j])//判断上点
{
if (A[i - 1, j] != 0)//上一点中已有值，则此点与上一点连通
{
A[i, j] = A[i - 1, j];
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//在左边缘，只需判断上面的元素
{
if (i > 0)//不在左上角
{
if (B[i - 1, j])
{
if (A[i - 1, j] != 0)//上一点中已有值，则此点与上一点连通
{
A[i, j] = A[i - 1, j];
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) });
}
}
}
}
}
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//不在第一行
{
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 if (B[i - 1, j - 1])//判断左上
{
if (A[i - 1, j - 1] != 0)//左上面有值，则此点与左上点连通
{
A[i, j] = A[i - 1, j - 1];
list[A[i, j] - 1].Add(new Point(i, j));
}
}
else if (B[i - 1, j])//判断上点
{
if (A[i - 1, j] != 0)//上一点中已有值，则此点与上一点连通
{
A[i, j] = A[i - 1, j];
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//在左边缘，只需判断上面的元素
{
if (i > 0)//不在左上角
{
if (B[i - 1, j])
{
if (A[i - 1, j] != 0)//上一点中已有值，则此点与上一点连通
{
A[i, j] = A[i - 1, j];
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) });
}
}
}
}
}
顺便鄙视一下师兄，居然不发300分的帖子
class SegmentationHelper
{
const int BACKGROUND = 255;
ushort[,] m_Data;
int m_Width;
int m_Height; public SegmentationHelper(Bitmap bmp)
{
if (bmp == null) throw new ArgumentException(); m_Width = bmp.Width + 2;
m_Height = bmp.Height + 2;
m_Data = new ushort[m_Width, m_Height]; BitmapData bmData = bmp.LockBits(
new Rectangle(0, 0, bmp.Width, bmp.Height),
ImageLockMode.ReadOnly,
PixelFormat.Format32bppArgb); IntPtr scan0 = bmData.Scan0;
int stride = bmData.Stride; for (int y = 0; y < bmp.Height; y++)
{
for (int x = 0; x < bmp.Width; x++)
{
int offset = y * stride + x * 4;
Color c = Color.FromArgb(Marshal.ReadInt32(scan0, offset));
m_Data[x + 1, y + 1] = (ushort)((c.R + c.G + c.B) / 3);
}
} bmp.UnlockBits(bmData); Segmentation();
} public void Binarize(int threshold)
{
for (int y = 1; y < m_Height - 1; y++)
{
for (int x = 1; x < m_Width - 1; x++)
{
m_Data[x, y] = (m_Data[x, y] >= threshold) ? ushort.MaxValue : ushort.MinValue;
}
}
} public Bitmap GetIndexedImage()
{
Bitmap bmp = new Bitmap(m_Width - 2, m_Height - 2, PixelFormat.Format8bppIndexed);
BitmapData bmData = bmp.LockBits(
new Rectangle(0, 0, bmp.Width, bmp.Height),
ImageLockMode.WriteOnly,
PixelFormat.Format8bppIndexed); IntPtr scan0 = bmData.Scan0;
int stride = bmData.Stride; for (int y = 0; y < bmp.Height; y++)
{
for (int x = 0; x < bmp.Width; x++)
{
int offset = y * stride + x;
Marshal.WriteByte(scan0, offset, (byte)(m_Data[x + 1, y + 1] & 0xff));
}
}
bmp.UnlockBits(bmData);
return bmp;
} static ushort GetNoneZeroMin(ushort a, ushort b)
{
if (a == 0) return b;
if (b == 0) return a;
return Math.Min(a, b);
} static void AddLink(ushort[] links, ushort a, ushort b)
{
if (a < b)
{
ushort swap = a;
a = b;
b = swap;
}
if (links[a] == 0)
{
links[a] = b;
}
else if (links[a] != b)
{
AddLink(links, links[a], b);
links[a] = b;
}
} int Segmentation()
{
ushort[] links = new ushort[ushort.MaxValue];
ushort = 1; for (int y = 1; y < m_Height - 1; y++)
{
for (int x = 1; x < m_Width - 1; x++)
{
// don't care about background pixel
if (m_Data[x, y] == BACKGROUND) continue; // the point
ushort upper = m_Data[x, y - 1];
ushort left = m_Data[x - 1, y];
m_Data[x, y] = GetNoneZeroMin(upper, left); // if upper and left neighbour have different label,
// add or modify an entry in the link table
if (upper != BACKGROUND && left != BACKGROUND && upper != left)
{
AddLink(links, upper, left);
} if (m_Data[x, y] == BACKGROUND)
{
m_Data[x, y] = ++;
if ( == ushort.MaxValue) throw new Exception("Maximal 65535 segments supported");
}
}//x
}//y // link table reconciliation
ushort[] compact = new ushort[];
for (ushort i = 1; i < ; i++)
{
if (links[i] == 0) links[i] = i;
else while (links[i] > links[links[i]]) links[i] = links[links[i]]; compact[links[i]] = 1;
} // compact groups
ushort groups = 0;
for (ushort i = 1; i < ; i++)
{
if (compact[i] > 0) compact[i] = ++groups;
} // label all pixels
for (int y = 1; y < m_Height - 1; y++)
{
for (int x = 1; x < m_Width - 1; x++)
{
m_Data[x, y] = compact[links[m_Data[x, y]]];
}
} return groups;
}
}
{
public Form1()
{
InitializeComponent();
} private const int M = 30;
private bool[,] B = new bool[M, M];
private List<List<Point>> P = new List<List<Point>>();
private List<Point>[] Temp = new List<Point>[M]; private void button1_Click(object sender, EventArgs e)
{
Random r = new Random();
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
int k = r.Next(0, 500);
B[i, j] = k < 150;
}
}
this.panel1.Invalidate();
P = new List<List<Point>>();
} private void panel1_Paint(object sender, PaintEventArgs e)
{
int gap = panel1.Width / M;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
if (B[i, j])
e.Graphics.FillRectangle(Brushes.Gray, j * gap, i * gap, gap, gap);
}
}
for (int i = 1; i < M; i++)
{
e.Graphics.DrawLine(Pens.Gray, i * gap, 0, i * gap, panel1.Width);
e.Graphics.DrawLine(Pens.Gray, 0, i * gap, panel1.Height, i * gap);
}
foreach (var pp in P)
{
Random r = new Random(Guid.NewGuid().GetHashCode());
Color c = Color.FromArgb(r.Next(0, 254), r.Next(0, 254), r.Next(0, 254));
using (var brush = new SolidBrush(c))
{
foreach (var p in pp)
e.Graphics.FillRectangle(brush, p.Y * gap, p.X * gap, gap, gap);
}
}
} private void Form1_Load(object sender, EventArgs e)
{
this.panel1.Invalidate();
} private void button2_Click(object sender, EventArgs e)
{
Stopwatch sw = new Stopwatch();
sw.Start();
P = new List<List<Point>>();
Temp = new List<Point>[M];
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
var leftIndex = j - 1 < 0 ? 0 : j - 1;
var rightIndex = j + 1 > M - 1 ? M - 1 : j + 1;
var curr = new Point(i, j);
#region first row handler
if (i == 0)
{
if (!B[i, j]) continue;
if (Temp[leftIndex] != null)
{
Temp[leftIndex].Add(curr);
Temp[j] = Temp[leftIndex];
}
else
{
Temp[j] = new List<Point> { curr };
P.Add(Temp[j]);
}
}
#endregion
#region other rows handler
else
{
if (B[i, j])
{
bool needNew = true;
bool removeRight = false;
if (Temp[leftIndex] != null &&
Temp[j] == null &&
Temp[rightIndex] != null &&
Temp[leftIndex] != Temp[rightIndex])
removeRight = true; if (Temp[leftIndex] != null)
{
Temp[leftIndex].Add(curr);
Temp[j] = Temp[leftIndex];
needNew = false;
}
else if (Temp[j] != null)
{
Temp[j].Add(curr);
needNew = false;
}
if (Temp[rightIndex] != null)
{
if (Temp[j] == null)
{
Temp[rightIndex].Add(curr);
Temp[j] = Temp[rightIndex];
}
else
{
if (removeRight)
P.Remove(Temp[rightIndex]);
Temp[j].AddRange(Temp[rightIndex]);
for (int x = rightIndex + 1; x < M; x++)
{
if (Temp[x] == Temp[rightIndex])
Temp[x] = Temp[j];
}
Temp[rightIndex] = Temp[j];
}
needNew = false;
} if (needNew)
{
Temp[j] = new List<Point> { curr };
P.Add(Temp[j]);
}
} if (j == M - 1)
{
for (int n = 0; n < M; n++)
if (!B[i, n]) Temp[n] = null;
}
}
#endregion
}
}
sw.Stop();
label1.Text = sw.ElapsedMilliseconds + "ms";
panel1.Invalidate();
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
class Program
{
struct Point
{
public int x, y;
Point(int _x = 0, int _y = 0){x=_x;y=_y;}
}
static List<List<Point>> get(bool[,] arr)
{
int N = arr.GetLength(0);
int M = arr.GetLength(1);
int[,] v = new int[N,M];
List<List<Point>> ret = new List<List<Point>>();
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j)
if (v[i,j] == 0 && arr[i,j])
{
v[i,j] = 1;
Queue<Point> q = new Queue<Point>();
Point init = new Point();
init.x = i; init.y = j;
q.Enqueue(init);
List<Point> l = new List<Point>();
while (q.Count > 0)
{
Point curr = q.Dequeue();
l.Add(curr);
for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy)
{
if (dx == 0 && dy == 0) continue;
int nx = curr.x + dx, ny = curr.y + dy;
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (v[nx,ny] == 1 || !arr[nx,ny]) continue;
v[nx,ny] = 1;
Point next = new Point();
next.x = nx; next.y = ny;
q.Enqueue(next);
}
}
ret.Add(l);
}
return ret;
}
static void Main(string[] args)
{
Random rnd = new Random();
bool[,] arr = new bool[100,40];
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
arr[i,j] = rnd.Next()%5 < 1;
int num = 0;
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
if (arr[i,j])++num;
List<List<Point>> ans = get(arr);
int tot = 0;
foreach(List<Point> c in ans)
{
string s = "";
foreach(Point p in c)
{
s += "(" + p.x + "," + p.y + ")";
++tot;
}
Console.WriteLine(s);
}
Console.WriteLine("{0},{1}", num, tot);
}
}
}
{
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));
}
}
}
}
}
}
应该可以不去考虑每个点它上面的3格和左边的1格，因为之前已经检测过了。
这样还剩下4个方向。然后再建一个二维bool数组Flag[,]，检测过的点竖个小旗，之后循环到可以跳过去。
未验证是否可行，有时间按这个思路写一下试试。
贴一个用递归来做的#include <iostream>using namespace std;int m , n ;
bool **map;void Input();
int GetPartNum();
void Clear(int x , int y);int main()
{
Input();
int num = GetPartNum();
cout<<num<<endl;
return 0;
}void Input()
{
cin>>m>>n;
map = new bool*[m];
for(int i = 0 ; i < m ; ++i)
{
map[i] = new bool[n];
for(int j = 0 ; j < n ; ++j)
{
cin>>map[i][j];
}
}
}int GetPartNum()
{
int num = 0 ;
for(int i = 0 ; i < m ; ++i)
{
for(int j = 0 ; j < n ; ++j)
{
if ( map[i][j] )
{
num ++ ;
Clear(i,j);
}
}
}
return num;
}void Clear(int x ,int y)
{
int xx,yy;
map[x][y] = 0;
for(int i = -1 ; i < 2 ; ++i)
{
for(int j = -1 ; j < 2 ; ++j )
{
if ( i == 0 && j == 0 ) continue ;
xx = x + i ;
yy = y + j ;
if ( xx >= 0 && xx < m && yy >= 0 && yy < n && map[xx][yy] )
Clear(xx,yy);
}
}
}
public static int I
{
get { return i++; }
set { i = value; }
}这个静态的变量作用就是给连通域编号。
然后定义一个int[,]大小和bool[,]一样，用来存放自识别信息。
接着就遍历bool[,]，如果为false，直接pass（你也可以设置为-1，表示比较过了）；如果为true，就看int[,]中对应位置是否大于0，如果大于0，说明该位置以及被编入了一个连通域，无需再去判断周围个节点情况，直接pass，如果等于0，说明该节点尚未被编入任何连通域，此时在int[,]中判断周围8个节点（边缘处不是8个），如果能找到一个大于0的节点，则在int[,]中的当前节点也设置那个大于0的值，相同值代表同一个连通域，如果周围8个节点都为0（并不是说对应的bool[,]中一定为false哦，只是那8个节点可能未设置过），那么在int[,]中的当前节点就获取一下全局的那个属性I，分配一个新的连通域值。特例：如果连通域是螺旋形的，可能会撞车，也就是分配的两个连通域值在之后有一次比较中被连通了，周围8个节点出现了两种大于0的值，此时需要再给一个变量，记录等价值，比如连通域1和连通域5发现可以连通，设置值的时候可以设置1或者5，并外部记录1和5连通。优势：这种算法优势很明显，第一、只需要一次遍历；第二、如果周围8个点全部判断一下的话，可以给周围8个点一起设置连通域值，这样下次遍历到那个节点时，可以直接跳过那个节点了；第三、整型值的操作效率很高。结语：我没专门学过算法，不知道我这个算法复杂度如何评估，知道的人可以帮我评估下。我想我描述得应该是很详细了，还有不理解的可以提出。
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 9;
int a[maxn+1][maxn+1];struct node
{
int beginx;
int endx;
int col;
node(int x,int y,int z):beginx(x),endx(y),col(z){}
};void init()
{
srand(time(NULL));//Ëæ»úÉú³É01¾ØÕó srand ( time(NULL) );
for(int i = 0; i < maxn; ++i)
for(int j = 0; j < maxn; ++j)
a[i][j] = rand()%2;
for(int i = 0; i < maxn; ++i)//²é¿´¾ØÕó
{
for(int j = 0; j < maxn; ++j)
cout << a[i][j];
cout << endl;
}
}int main()
{
init();
stack<node> mystack;
vector<node> myvector;
for(int i = 0; i < maxn; ++i)
{
int sum = 1;
int c = i;
for(int j = 0; j < maxn; ++j)
{
if(a[i][j] && a[i][j+1])
{
++sum;
}
else if(a[i][j])
{
myvector.push_back(node(j-sum+1,j,c));
sum = 1;
}
}
}
cout << "********************" << endl;
//for(int i = 0; i < myvector.size(); ++i)
//cout << myvector[i].beginx << " " << myvector[i].endx << " " << myvector[i].col << endl;
int f[1000] = {0};//±ê¼ÇÊÇ·ñÒѾ±»·ÃÎʹý
int k = 1;
int cc[1000] = {0};
for(int i = 0; i < myvector.size(); ++i)
{
if(!f[i])
{
mystack.push(myvector[i]);
f[i] = 1;
cc[i] = k;
//cout << i << ",!" << k << endl;
}
while(!mystack.empty())
{
int b = 1;
node op = mystack.top();
for(int i = 0; i < myvector.size(); ++i)
{
node ok = myvector[i];
if(ok.col+1 == op.col || ok.col-1 == op.col)//ÊÇ·ñÊÇÔÚ¸ÃÐеÄÉÏÏÂÐÐ
{
if(!f[i] && op.beginx-1 <= ok.endx && op.endx+1 >= ok.beginx)//Èç¹ûÁ¬Í¨
{
mystack.push(myvector[i]);
f[i] = 1;
cc[i] = k;
//cout << i << ",?" << k << endl;
b = 0;
}
}
}
if(b)mystack.pop();
}
++k;
}
for(int i = 0; i < myvector.size(); ++i)
{
for(int j = myvector[i].beginx; j <= myvector[i].endx; ++j)
a[myvector[i].col][j] = cc[i];
}
for(int i = 0; i < maxn; ++i)//²é¿´¾ØÕó
{
for(int j = 0; j < maxn; ++j)
cout << a[i][j];
cout << endl;
}
return 0;
}
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
class Program
{ static List<List<Point>> GetNumber(bool[,] MyArr)
{
int x = MyArr.GetLength(0);
int y = MyArr.GetLength(1);
int[,] Mark = new int[x, y];
Mark.Initialize();
List<List<Point>> list = new List<List<Point>>();
Queue<Point> MyQueue = new Queue<Point>();
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
if (MyArr[i, j] == false) continue;
if (Mark[i, j] == 1) continue;
else
{
List<Point> tmpList = new List<Point>();
tmpList.Add(new Point(i, j)); Mark[i, j] = 1;
MyQueue.Enqueue(new Point(i, j));
while (MyQueue.Count > 0)
{
Point _p = MyQueue.Dequeue();
int tx = _p.x - 1, ty = _p.y - 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x - 1; ty = _p.y; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x - 1; ty = _p.y + 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x; ty = _p.y - 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x; ty = _p.y + 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x + 1; ty = _p.y - 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x + 1; ty = _p.y; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
tx = _p.x + 1; ty = _p.y + 1; NewMethod(MyArr, x, y, Mark, MyQueue, tmpList, tx, ty);
}
list.Add(tmpList);
} }
} return list;
} private static void NewMethod(bool[,] MyArr, int x, int y, int[,] Mark, Queue<Point> MyQueue, List<Point> tmpList, int tx, int ty)
{
if (tx >= 0 && tx < x && ty < y && ty >= 0 && MyArr[tx, ty] == true && Mark[tx, ty] == 0)
{
tmpList.Add(new Point(tx, ty));
Mark[tx, ty] = 1;
MyQueue.Enqueue(new Point(tx, ty));
}
} static void Main(string[] args)
{
Random rnd = new Random();
bool[,] arr = new bool[100, 40];
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
arr[i, j] = rnd.Next() % 5 < 1;
int num = 0;
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
if (arr[i, j]) ++num;
List<List<Point>> ans = GetNumber(arr);
int tot = 0;
foreach (List<Point> c in ans)
{
string s = "";
foreach (Point p in c)
{
s += "(" + p.x + "," + p.y + ")";
++tot;
}
Console.WriteLine(s);
}
Console.WriteLine("{0},{1}", num, tot);
}
} struct Point
{
public int x;
public int y;
public Point(int _xx, int _yy)
{
this.x = _xx;
this.y = _yy;
}
}
}
我的代码很邪恶？
//倒，之前的代码忘了在构造函数前加public了导致只能new一个赋值，所以代码有些不好看，重新改一下。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
class Program
{
struct Point
{
public int x, y;
public Point(int _x = 0, int _y = 0){x=_x;y=_y;}
}
static List<List<Point>> get(bool[,] arr)
{
int N = arr.GetLength(0);
int M = arr.GetLength(1);
int[,] v = new int[N,M];
List<List<Point>> ret = new List<List<Point>>();
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j)
if (v[i,j] == 0 && arr[i,j])
{
v[i,j] = 1;
Queue<Point> q = new Queue<Point>();
q.Enqueue(new Point(i, j));
List<Point> l = new List<Point>();
while (q.Count > 0)
{
Point curr = q.Dequeue();
l.Add(curr);
for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy)
{
if (dx == 0 && dy == 0) continue;
int nx = curr.x + dx, ny = curr.y + dy;
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (v[nx,ny] == 1 || !arr[nx,ny]) continue;
v[nx,ny] = 1;
q.Enqueue(new Point(nx, ny));
}
}
ret.Add(l);
}
return ret;
}
static void Main(string[] args)
{
Random rnd = new Random();
bool[,] arr = new bool[100,40];
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
arr[i,j] = rnd.Next()%5 < 1;
int num = 0;
for (int i = 0; i < 100; ++i) for (int j = 0; j < 40; ++j)
if (arr[i,j])++num;
List<List<Point>> ans = get(arr);
int tot = 0;
foreach(List<Point> c in ans)
{
string s = "";
foreach(Point p in c)
{
s += "(" + p.x + "," + p.y + ")";
++tot;
}
Console.WriteLine(s);
}
Console.WriteLine("{0},{1}", num, tot);
}
}
}
递归，不知效率如何。
void CFindConnectionDoc::OnFindConnection()
{
// TODO: 在此添加命令处理程序代码
for (int y = 0; y < Y_MAX; ++y)
for (int x = 0; x < X_MAX; ++x)
{
findConnection(y, x, RGB(10 * x % 255 + 50, 20 * y % 255 + 50, x*y%255 + 120));
} UpdateAllViews(NULL);
}bool CFindConnectionDoc::findConnection( int x, int y, COLORREF color)
{
if (x < 0 || y < 0 || x >= X_MAX || y >= Y_MAX)
{
return false;
}
if (m_tiles[y][x] == -1)
{
m_tiles[y][x] = color;
findConnection(x - 1, y - 1, color);
findConnection(x, y - 1, color);
findConnection(x + 1, y -1, color) ;
findConnection(x - 1, y, color) ;
findConnection(x + 1, y, color) ;
findConnection(x - 1, y + 1, color) ;
findConnection(x, y + 1, color) ;
findConnection(x + 1, y + 1, color);
} return false;
}
void CFindConnectionDoc::OnRandom()
{
// TODO: 在此添加命令处理程序代码
srand((unsigned int)time(NULL));
// TODO: 在此添加一次性构造代码
for (int y = 0; y < Y_MAX; ++y)
for (int x = 0; x < X_MAX; ++x)
{
m_tiles[y][x] = rand() % 10 > 5 ? -1 : 0;
}
UpdateAllViews(NULL);}
图
也就是0(m*n)的啊！用BFS搜索一遍就可以了！
acm里的确好多这样的问题！