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ビットのセットを表すということです（必要に応じて、ビットマップ）。
現在、ビットのすべての可能な組み合わせが有効であるとは限りません。私にはいくつかの要件があります：
size合計はビットのみである必要があります。（これは簡単です、私はすでにこれを実装しました）- すべてのビットは連続している必要があります。
したがって、再び仮定size==4すると、次のことが適切です。
..#.
..#.
.##.
....
以下はそうではありませんが：
...#
...#
#...
#...
すべてのビットが隣接しているかどうかを判断するにはどうすればよいですか？
編集：これがEricLippertの答えを組み込んだ完全なコードです。これは、パフォーマンスの面で確実に強化できますが、非常に読みやすくなっています。
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
}