Есть ли более быстрый способ проверить, образуют ли 0 битборда полимино? ⇐ C#

[Anonymous]

Метод, который я использую, очень прост для понимания, и я не уверен, как можно сделать его быстрее, но, возможно, есть другой метод. Я пытаюсь выяснить, образуют ли все 0 битборда полимино. Определение, которое я использую, — это любое расположение квадратов, при котором все они соединены ребрами. Я не дисквалифицирую его не потому, что я уже видел его зеркальную, повернутую версию, или потому, что он был перевернут или имеет дырку.
Я делаю это, подсчитывая количество нулей. Затем я нахожу первый 0 и оттуда выполняю поиск всего, что соединено ребром. Если количество найденных ячеек равно количеству нулей, то это было полимино. В противном случае были бы ячейки, до которых он не мог бы добраться, и, следовательно, это не было бы полимино.
Еще одна идея заключалась в том, чтобы пройтись по каждой строке и найти островки из нулей. Чтобы было легче понять, я бы инвертировал его и попытался найти островки из единиц.
Скажем, у нас есть две строки:
1 1 1 0 0 1 1 1
0 0 1 1 1 1 0 0
Первая строка содержит два острова: 11100000 и 00000111, которые я обозначим a и b. Во второй строке всего один остров 00111100, который я назову c.
Если I AND a и c, то я могу сказать, что они связаны, потому что у них есть общие элементы. Это a И c > 0. Далее, b и c также больше 0. Это означает, что я могу объединить острова a и b. А затем повторите. По сути, пройдитесь по каждому острову и любому другому острову и объедините их, если у них есть что-то общее. Когда это будет сделано, если каждая строка будет объединена в один остров, то это будет полимино. Я просто не уверен, что это будет быстрее, потому что разбить его на острова кажется большой работой.
Я индексирую битборд, начиная с верхнего левого угла. , идя слева направо. Таким образом, индекс + 1 – это ячейка справа от индекса, а индекс – 8 – это ячейка над индексом.
public static bool PolyominoChecker(ulong bitboard)
{
// This should count the zeros
int population = 64 - BitOperations.PopCount(bitboard);

HashSet visited = new HashSet();
Queue queue = new Queue();

// Gets the first empty cell
visited.Add(BitOperations.TrailingZeroCount(~bitboard));
queue.Enqueue(BitOperations.TrailingZeroCount(~bitboard));

// This is a basic BFS
while (queue.Count > 0)
{
int index = queue.Dequeue();
// Checks the cell left of index
if(index % 8 > 0 && GetBitboardCell(bitboard, index - 1) == false)
{
if (!visited.Contains(index - 1))
{
visited.Add(index - 1);
queue.Enqueue(index - 1);
}
}
// Check the cell above index
if (index >= 8 && GetBitboardCell(bitboard, index - 8) == false)
{
if (!visited.Contains(index - 8))
{
visited.Add(index - 8);
queue.Enqueue(index - 8);
}
}
if (index + 8 < 64 && GetBitboardCell(bitboard, index + 8) == false)
{
if (!visited.Contains(index + 8))
{
visited.Add(index + 8);
queue.Enqueue(index + 8);
}
}
if (index % 8 < 7 && GetBitboardCell(bitboard, index + 1) == false)
{
if (!visited.Contains(index + 1))
{
visited.Add(index + 1);
queue.Enqueue(index + 1);
}
}
}

// If we visit all the empty cells, then it will equal the population of the empty cells
return visited.Count == population

public static bool GetBitboardCell(ulong bitboard, int index)
{
return (bitboard & (1UL

Подробнее здесь: https://stackoverflow.com/questions/793 ... -polyomino