лучший алгоритм для проверки 5 в строке / col в матрице

Question

Есть ли хороший алгоритм для проверки, есть ли 5 ​​одинаковых элементов в строке или столбце или по диагонали с заданной квадратной матрицей, скажем, 6x6?

Конечно, существует наивный алгоритм итерации по каждой точке изатем для каждой точки в матрице, итерации по этой строке, col, а затем по диагонали.Мне интересно, есть ли лучший способ сделать это.

Answer 1

Вы можете хранить гистограмму в словаре (тип элемента отображения -> int). Затем вы перебираете строку или столбец или диагональ и увеличиваете histogram[element], и либо проверяете в конце, чтобы увидеть, есть ли у вас 5 гистограмм, или если вы можете разрешить более 5 копий, вы можете просто остановиться один раз. Вы достигли 5 для любого элемента.

Простой, одномерный, пример:

m = ['A', 'A', 'A', 'A', 'B', 'A']

h = {}
for x in m:
    if x in h:
        h[x] += 1
    else:
        h[x] = 1

print "Histogram:", h

for k in h:
    if h[k]>=5:
        print "%s appears %d times." % (k,h[k])

Выход:

Histogram: {'A': 5, 'B': 1}
A appears 5 times.

По сути, h[x] будет хранить количество раз, когда элемент x появляется в массиве (в вашем случае это будет текущая строка, столбец или диагональ). Элементы не должны появляться последовательно, но счет будет сбрасываться каждый раз, когда вы начинаете рассматривать новую строку / столбец / диагональ.

Answer 2

Вы можете проверить, есть ли k одинаковых элементов в матрице целых чисел в однократном проходе .

Предположим, что n - это размер матрицы, а m - самый большой элемент.У нас есть n столбца, n строки и 1 диагональ.Для каждого столбца, строки или диагонали мы имеем не более n различных элементов.

Теперь мы можем создать гистограмму, содержащую (n + n + 1) * (2 * m + 1) элемент.Представляя строки, столбцы и диагонали, каждая из которых содержит не более n различных элементов.

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

Теперь самое сложное, как обновить эту гистограмму?

Рассмотрим эту функцию в псевдо-code:

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

Теперь все, что вам нужно сделать, - это выполнить итерацию, выбросить гистограмму и проверить, есть ли элемент> k

Answer 3

Если вы кодируете строки / столбцы / диагонали как растровые изображения, «пять в ряд» означает «маска% 31 == 0 && mask / 31 == power_of_two»

• 00011111: = 0x1f 31 (пять подряд)
• 00111110: = 0x3e 62 (пять подряд)
• 00111111: = 0x3f 63 (шесть подряд)

Если вы хотите рассматривать случай с шестью рядами также как случай с пятью рядами, возможно, самый простой способ:

for ( ; !(mask & 1) ; mask >>= 1 ) {;}
return (mask & 0x1f == 0x1f) ? 1 : 0;

Может быть, в отделе бит-твикинга в Стэнфорде есть лучшее решение или предложение, которое не нуждается в цикле?

Answer 4

Вы можете попытаться улучшить свой метод с помощью некоторой эвристики: используйте знание размера матрицы, чтобы исключить последовательности элементов, которые не соответствуют, и приостановить ненужные вычисления. Если заданный размер вектора равен 6, необходимо найти 5 равных элементов, а первые 3 элемента отличаются, дальнейшие вычисления не имеют никакого смысла.

Этот подход может дать вам значительное преимущество, если 5 одинаковых элементов подряд встречаются достаточно редко.

Answer 5

Я не думаю, что вы можете избежать итерации, но вы можете, по крайней мере, сделать XOR для всех элементов, и если результат равен 0 =>, они все равны, тогда вам не нужно делать никаких сравнений.

Answer 6

Ваш лучший подход может зависеть от того, управляете ли вы размещением элементов.

Например, если вы строили игру и просто поместили самый последний элемент в сетку, вы можете записать в четыре строки:вертикальные, горизонтальные и диагональные полосы, которые пересекали эту точку и используют один и тот же алгоритм на каждой полосе, подсчитывая каждый элемент и оценивая итоги.Алгоритм может немного отличаться в зависимости от того, считаете ли вы пять смежных элементов из шести или допускаете пропуски, если общее количество равно пяти.

Answer 7

Для строк вы можете сохранить счетчик, который указывает, сколько одинаковых элементов в строке у вас есть в данный момент. Для этого выполните итерацию по строке и

• , если текущий элемент соответствует предыдущему элементу, увеличить счетчик на единицу. Если счетчик равен 5, то вы нашли 5 элементов, которые хотели.
• если текущий элемент не соответствует предыдущему элементу, установите счетчик на 1.

Тот же принцип применим и к колоннам и диагоналям. Возможно, вы захотите использовать массив счетчиков для столбцов (по одному элементу для каждого столбца) и диагоналей, чтобы можно было выполнить итерацию по матрице один раз.

Я сделал небольшой пример для меньшего случая, но вы можете легко изменить его:

n = 3
matrix = [[1, 2, 3, 4], 
          [1, 2, 3, 1], 
          [2, 3, 1, 3],
          [2, 1, 4, 2]]
col_counter = [1, 1, 1, 1]
for row in range(0, len(matrix)):
    row_counter = 1
    for col in range(0, len(matrix[row])):
        current_element = matrix[row][col]

        # check elements in a same row
        if col > 0:
            previous_element = matrix[row][col - 1]
            if current_element == previous_element:
                row_counter = row_counter + 1
                if row_counter == n:
                    print n, 'in a row at:', row, col - n + 1
            else:
                row_counter = 1

        # check elements in a same column
        if row > 0:
            previous_element = matrix[row - 1][col]
            if current_element == previous_element:
                col_counter[col] = col_counter[col] + 1;
                if col_counter[col] == n:
                    print n, 'in a column at:', row - n + 1, col
            else:
                col_counter[col] = 1

Я оставил диагонали, чтобы пример был коротким и простым, но для диагоналей вы можете использовать тот же принцип, что и для столбцов. Предыдущий элемент будет одним из следующих (в зависимости от направления диагонали):

matrix[row - 1][col - 1]
matrix[row - 1][col + 1]

Обратите внимание, что вам нужно будет приложить немного дополнительных усилий во втором случае. Например, пройти строку во внутреннем цикле справа налево.