Mik*_*ron 2 c# boolean bitmap area
假设您在C#中具有以下结构:
struct Piece : IEquatable<Piece> {
public readonly int size;
public readonly bool[,] data;
public Piece(Piece p) {
size = p.size;
data = (bool[,])p.data.Clone();
}
public Piece(int s, bool[,] d) {
size = s;
if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();
data = (bool[,])d.Clone();
}
public bool Equals(Piece other) {
if (size != other.size) return false;
return (data.Equals(other.data));
}
}
这个想法是它代表一组sizex size位代表一个形状(一个位图,如果你愿意的话).
现在,并非所有可能的位组合都有效.我有一些要求:
size位总数.(这很简单,我已经实现了这个)所以,再次假设size==4,以下是好的:
..#.
..#.
.##.
....
虽然以下不是:
...#
...#
#...
#...
如何确定所有位是否连续？
编辑:这是完整的代码,结合Eric Lippert的答案.这绝对可以在性能方面得到收紧,但它非常易读.
struct Point : IEquatable<Point> {
public int X, Y;
public Point(int x, int y) {
X = x; Y = y;
}
public bool Equals(Point obj) {
return X == obj.X && Y == obj.Y;
}
public override bool Equals(object obj) {
if (obj == null) return false;
if(obj is Point)
return Equals((Point)obj);
return false;
}
public override int GetHashCode() {
return X ^ ~Y;
}
public static bool operator == (Point p1, Point p2) {
return p1.X == p2.X && p1.Y == p2.Y;
}
public static bool operator !=(Point p1, Point p2) {
return p1.X != p2.X || p1.Y != p2.Y;
}
public static readonly Point Empty = new Point(int.MinValue, int.MinValue);
}
struct Piece : IEquatable<Piece> {
public readonly int size;
public readonly bool[,] data;
private bool valid;
public Piece(Piece p) {
size = p.size;
valid = p.valid;
data = (bool[,])p.data.Clone();
}
public Piece(int s, bool[,] d) {
size = s;
if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();
data = (bool[,])d.Clone();
valid = false;
CalcValidity();
}
public bool IsValid {
get {
return valid;
}
}
private enum Square {
White,
Black,
Red,
Blue,
}
private int NumSquares(Square[,] map, Square q) {
int ret = 0;
for (int y = 0; y < size; y++) {
for(int x = 0; x < size; x++) {
if (map[x, y] == q) ret++;
}
}
return ret;
}
private Point PickSquare(Square[,] map, Square q) {
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (map[x, y] == q) return new Point(x, y);
}
}
return Point.Empty;
}
private void MakeNeighboursRed(Square[,] map, Point p) {
if (p.X > 0 && map[p.X - 1, p.Y] == Square.Black) map[p.X - 1, p.Y] = Square.Red;
if (p.X < size - 1 && map[p.X + 1, p.Y] == Square.Black) map[p.X + 1, p.Y] = Square.Red;
if (p.Y > 0 && map[p.X, p.Y - 1] == Square.Black) map[p.X, p.Y - 1] = Square.Red;
if (p.Y < size - 1 && map[p.X, p.Y + 1] == Square.Black) map[p.X, p.Y + 1] = Square.Red;
}
private void CalcValidity() {
Square[,] map = new Square[size, size];
int count = 0;
Point square = Point.Empty;
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (data[x, y]) {
map[x, y] = Square.Black;
square = new Point(x, y);
} else {
map[x, y] = Square.White;
}
}
}
if (square != Point.Empty) {
map[square.X, square.Y] = Square.Red;
}
while (true) {
if (NumSquares(map, Square.Red) == 0) {
if (NumSquares(map, Square.Black) == 0) {
valid = count == size;
return;
} else {
valid = false;
return;
}
} else {
square = PickSquare(map, Square.Red);
MakeNeighboursRed(map, square);
map[square.X, square.Y] = Square.Blue;
count++;
}
}
}
#region IEquatable<Piece> Members
public bool Equals(Piece other) {
if (size != other.size) return false;
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (data[x, y] != other.data[x, y]) return false;
}
}
return true;
}
#endregion
}
这是一种考虑不使用递归的泛洪填充算法的方法.
从每个方块设置为白色(空白)或黑色(填充)开始.问题是"黑色区域是否连续？"
您可以使用此算法:
看看它是如何工作的？红色方块是该区域的"边缘",没有充满洪水.蓝色方块是淹水区域.如果蓝色泛滥全黑,那么它一定是连续的.
更新:Re,你的评论:
非常感谢!太棒了.我喜欢你的博客,特别是关于LINQ和"写你的意思"的文章,我试着在这里应用这些原则
感谢您的客气话.如果你喜欢的是这些问题的非常"LINQ-y"解决方案,那么我就不会使用我在这里概述的解决方案.请注意,该算法基本上是"改变数据结构以了解它的事实".这不是一个非常LINQ的事情.LINQ就是在不修改数据结构的情况下查询数据结构.
如果我想为你的问题制作更像LINQ的解决方案,那么我会采取一种非常不同的方法.这就是我要做的.
首先,你知道什么是"等价类"或"等价关系"吗？如果你不知道,我会简要定义它们.一个关系是一个函数,两件事情并返回一个布尔值.例如,"小于","等于","在十进制中具有相同的最后一位"和"与偶数相加"都是整数上的关系.一个等价关系(A〜B)是一个关系是自反(X〜X总是为真),对称(X〜Y和Y〜X是相同的)和传递(如果X〜Y和Y〜Z都为真那么是X~Z).
在我们的例子中,"小于"是可传递的但不是反身的或对称的.其他三个是等价关系.
等价关系将集合划分为等价类.例如,等价关系"sum to a even number"将整数划分为两个等价类:偶数和奇数.选择任意两个奇数,X~Y为真.选择任意两个偶数,X~Y为真.但是奇数和偶数,X~Y是假的.出于这种关系的目的,所有偶数都是"等价的".
现在考虑其中一个图块集的关系"是此图块集上的邻居".显然,这不是等价关系; 它是对称的,但不是反身的或传递的.但是,任何关系都可以通过定义一个新关系来扩展为等价关系,这种关系是关系的自反和传递闭包.这是"可以达到"的关系.
因此,你的问题基本上是"可达性的等价关系有多少等价类"？如果答案为零则没有黑色区域.如果答案是1,则存在单个连续区域.如果它不止一个那么必须有不连续的区域.
因此,表征你的问题的另一种方法是"假设至少有一个黑色瓷砖,整个黑色瓷砖组与任意瓷砖上相邻关系的反射和传递闭合相同吗？" 如果答案是"是",则存在单个连续区域.如果"否"则必须存在无法访问的区域.
既然你有办法计算瓷砖,并且由于数字是有限整数,我们可以做得更好.我们可以问一下"任意黑色瓷砖上相邻关系的反射和传递闭合的大小是否与所有黑色瓷砖的数量相同？" 解决你的问题.
那么如何回答这个问题呢？假设您有一个方法,它接受一个tile并返回其邻居的序列:
public static IEnumerable<Tile> GetNeighbours(Tile tile)
{
... yield return the north, south, east and west neighbours
... if they exist and they are on
}
基本上这个方法是"给一个瓦片,给我所有与它有邻居关系的瓦片".如果您可以计算哪些成员与给定成员有关系,这很有用,在这种情况下,您可以很便宜地这样做.
现在,您可以使用我在此处发布的代码计算该关系的传递和自反闭包:
http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx
现在你的整个算法确实很短:
bool HasExactlyOneRegion()
{
return (tilesTurnedOn.Count == 0) ?
false :
TransitiveAndReflexiveClosure(GetNeighbours, tilesTurnedOn.First()).Count == tilesTurnedOn.Count;
}
如果您有合适的工具,那么解决方案就是一个声明!
请注意,我给出的两个解决方案(以及Albin的草图)在操作上是相同的.在我的第二个解决方案中,第一个解决方案的"红色磁贴"是"堆栈"数据结构中的磁贴,而"蓝色磁贴"是我给出的链接中代码的"闭包"数据结构中的磁贴.
解决方案之间的区别仅在于您如何看待解决方案.我喜欢用数学思考,所以我更喜欢第二种解决方案.这一切都与集合,关系和闭包,非常抽象的想法有关.如果你更像是一个视觉思想家,那么我的第一个解决方案可以更容易理解和推理,在那里你可以看到一个红色边缘波蔓延到一个黑色区域,直到它满了.