如何验证二维位图是否连续？

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));
    }
}

其思想是它表示一个 sizexsize 位集，该位集表示一个形状（如果愿意，可以是位图） 。

现在，并非所有可能的位组合都是有效的。我有一些要求：

1. 总共必须只有 size 位。 （这很简单，我已经实现了）
2. 所有位必须是连续的。

因此，再次假设 size==4，以下内容是好的：

..#.
..#.
.##.
....

而以下内容则不然：

...#
...#
#...
#...

如何确定所有位是​​否连续？

编辑：这是完整的代码，包含埃里克·利珀特的答案。从性能角度来看，这绝对可以加强，但它的可读性很强。

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

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

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

您可以使用以下算法：

1. 如果没有黑色方块，则确实不存在不连续的黑色区域，所以您就完成了。
2. 否则，至少有一个黑色方块。选择任何黑色方块并将其变成红色。
3. 如果没有红色方块，也没有黑色方块，那么您就完成了，并且黑色区域是连续的。
4. 如果没有红色方块，只有一个或多个黑色方块，那么您就完成了。黑色区域不连续。仍然是黑色的区域与蓝色区域不连续。
5. 否则，必须至少有一个红色方块。选择任何红色方块。将其所有黑色邻居变为红色，然后将其变为蓝色。
6. 返回第 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为假。就该关系而言，所有偶数都是“相等的”。

现在考虑您的图块集之一的关系“是该图块集上的邻居”。显然这不是等价关系；它是对称的，但不是自反或传递的。但是，任何关系都可以通过定义一个新关系来扩展为等价关系，该新关系是该关系的自反和传递闭包。这就是“可达”关系。

因此，您的问题本质上是“可达性的等价关系有多少个等价类”？如果答案为零，则不存在黑色区域。如果答案是 1，则存在一个连续区域。如果超过一个，则必定存在不连续的区域。

因此，描述你的问题的另一种方法是“假设至少有一个黑色瓷砖，整组黑色瓷砖是否与任意瓷砖上邻居关系的自反和传递闭包相同？”如果答案是“是”，则存在一个连续区域。如果“否”，则一定存在不可到达的区域。

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

那么如何回答这个问题呢？假设你有一个方法，它接受一个图块并返回其邻居的序列：

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;
}

如果你有合适的工具可供使用，那么解决方案就是一个语句！

请注意，我给出的两个解决方案（以及阿尔宾的草图）的操作相同。在我的第二个解决方案中，第一个解决方案的“红色图块”是“堆栈”数据结构中的图块，“蓝色图块”是我给出的链接中代码的“闭包”数据结构中的图块。

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

Answer 2

您从随机的“真实”位开始。然后你一次向北、向南、向东、向西“行走”。如果您发现未“访问”的“真实”位，请在单独的结构中将该节点标记为“已访问”，并从那里沿所有方向递归“行走”。如果该位为“假”或“已访问”，则不执行任何操作并返回到先前的“级别”。当找不到更多非“已访问”节点时，计算已访问节点的数量并与“真实”节点的总数进行比较。

编辑：请注意，如果位图很大，递归将耗尽堆栈空间。