2

假设您在 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,以下是好的:

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

虽然以下不是:

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

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

编辑:这是完整的代码,包含 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
}
4

2 回答 2

6

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

从将每个正方形设置为白色(空白)或黑色(填充)开始。问题是“黑色区域是否连续?”

您可以使用此算法:

  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 是假的。出于这种关系的目的,所有偶数都是“等价的”。

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

因此,您的问题本质上是“可达性的等价关系有多少等价类”?如果答案为零,则没有黑色区域。如果答案是一个,那么就有一个连续的区域。如果它不止一个,则必须有不连续的区域。

因此,描述您的问题的另一种方法是“假设至少有一个黑色瓷砖,整个黑色瓷砖集是否与任意瓷砖上的邻居关系的自反和传递闭包相同?” 如果答案是“是”,那么就有一个连续的区域。如果“否”,则必须有一个不可到达的区域。

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

那么如何回答这个问题呢?假设您有一个方法,该方法接受一个图块并返回其邻居序列:

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 的草图)在操作上是相同的。在我的第二个解决方案中,第一个解决方案的“红色瓷砖”是“堆栈”数据结构中的瓷砖,而“蓝色瓷砖”是我给出的链接中代码的“闭包”数据结构中的瓷砖。

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

于 2010-09-10T21:18:13.873 回答
0

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

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

于 2010-09-10T20:08:40.077 回答