c# - 您如何验证2d位图是连续的？

Question

假设您在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));
    }
}

这个想法是，它代表一组表示形状的size x 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
}

Answer 1

这是一种考虑不使用递归的泛洪填充算法的方法。

首先将每个正方形设置为白色（空白）或黑色（实心）。问题是“黑色区域是否连续？”

您可以使用以下算法：


如果没有黑色方块，那么确实没有不连续的黑色区域，那么就完成了。
否则，至少有一个黑色正方形。选择任何黑色正方形并将其变为红色。
如果没有红色方块，也没有黑色方块，则说明操作完成，并且黑色区域是连续的。
如果没有红色方块，但有一个或多个黑色方块，那么您就完成了。黑色区域不连续。仍然是黑色的区域与蓝色的区域是不连续的。
否则，必须至少有一个红色正方形。选择任何红色正方形。将其所有黑色邻居变为红色，然后将其变为蓝色。
返回步骤3。


看看如何运作？红色方块是未充满洪水的区域的“边缘”。蓝色方块是水淹区域。如果蓝色泛滥了所有黑色，那么它一定是连续的。

更新：回复，您的评论：


非常感谢！太棒了。我喜欢您的博客，尤其是有关LINQ和“写出您的意思”的文章，我尝试在此处应用这些原则


感谢您的客气话。如果您喜欢针对此类问题的非常“ LINQ-y”解决方案，那么我将不使用在此勾勒出的解决方案。请注意，该算法基本上是“对数据结构进行变异以了解其事实”。这不是一件很LINQ的事情。 LINQ只是关于查询数据结构而不修改它们。

如果我想为您的问题提供更像LINQ的解决方案，那么我将采用一种非常不同的方法。这就是我要做的。

首先，您知道什么是“等价类”或“等价关系”吗？如果您不知道，我将简要定义它们。关系是需要两件事并返回布尔值的函数。例如，“小于”，“等于”，“以十进制表示的最后一位相同”和“总和为偶数”都是整数上的关系。等价关系（A〜B）是自反（X〜X始终为真），对称（X〜Y和Y〜X相同）和传递（如果X〜Y和Y〜Z都为真）的关系X〜Z也是如此）

在我们的示例中，“小于”是传递的，但不是反身的或对称的。其他三个是等价关系。

等价关系将集合划分为等价类。例如，等价关系“总和为偶数”将整数划分为两个等价类：偶数和奇数。选择任意两个奇数，X〜Y为真。选择任意两个偶数，X〜Y为真。但是X〜Y是奇数和偶数，是错误的。就此关系而言，所有偶数都是“等效的”。

现在考虑其中一个图块集的关系“该图块集上的邻居”。显然，这不是等价关系；它是对称的，但不是反身或传递的。但是，通过定义新的关系（即该关系的自反和及物闭合），可以将任何关系扩展为等价关系。这是“可以从”到达的关系。

因此，您的问题实质上是“可达性的等价关系有多少个等价类”？如果答案为零，则没有黑色区域。如果答案是一个，则只有一个连续的区域。如果不止一个，则必须有不连续的区域。

因此，表征您的问题的另一种方式是“假设至少有一个黑色图块，那么整个黑色图块集合是否与任意图块上的邻居关系的反射性和传递性封闭完全相同？”如果答案为“是”，则存在单个连续区域。如果为“否”，则必须存在一个无法到达的区域。

由于您可以计算图块，并且数字是有限整数，因此我们可以做得更好。我们可以问：“任意黑色图块上邻居关系的自反和及物传递闭合的大小是否与所有黑色图块的数量相同？”解决您的问题。

那么如何回答这个问题呢？假设您有一个方法，该方法接受一个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的草图）在操作上是相同的。在我的第二个解决方案中，第一个解决方案的“红色图块”是“堆栈”数据结构中的图块，而“蓝色图块”是我给出的链接中的代码“闭合”数据结构中的图块。

解决方案之间的区别仅在于您对解决方案的看法。我喜欢用数学的方式思考，所以我更喜欢第二种解决方案。这一切都是关于集合，关系和闭包，非常抽象的想法。如果您更像是一个视觉思想家，那么我的第一个解决方案可能更容易理解和推论，在该解决方案中，您可以看到一个红色边缘的波，该波扩散到黑色区域直到充满为止。