Let's say you have the following structure in 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));
}
}
The idea is that it represents a sizexsize set of bits which represents a shape (a bit map, if you will).
Now, not all possible combinations of bits are valid. I have a few requirements:
- There must be only
sizebits total. (This is easy, I have already implemented this) - All bits must be contiguous.
So, again assuming size==4, the following is good:
..#.
..#.
.##.
....
While the following is not:
...#
...#
#...
#...
How do I determine whether all the bits are contiguous or not?
Edit: Here is the full code, incorporating Eric Lippert's answer. This can definitely be tightened up, performance-wise, but it's very readable.
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
}