Как эффективнее проверить наличие полос на игровом поле?

Question

Следующая функция получает двумерный массив следующим образом.

[['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', 'y', '.', '.', '.', '.'],
 ['.', '.', 'y', '.', 'r', '.', 'y'],
 ['.', 'r', 'r', 'y', 'r', 'y', 'r'],
 ['.', 'r', 'y', 'y', 'r', 'r', 'y']]

Цель функции - подсчитать количество «полос» определенного размера, которые существуют в моем 2D-массиве. Полоса определяется как последовательная линия токенов в горизонтальном, вертикальном или диагональном расположении.

Следующий пример считается за 1 полосу размером 2.

[['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', 'r', '.', '.', '.', '.'],
 ['.', 'r', '.', '.', '.', '.', '.']]

Следующий фрагмент - мое решение для грубой силы, которое проходит через каждую комбинацию доски. Есть ли более эффективное решение / алгоритм, который я могу использовать вместо этого?

def streaks(num_repeats, board, player_color):    
    reduced_range = num_repeats - 1
    list_idx_offsets = list(range(0, num_repeats))
    counter = 0
    # Checks rows
    for col in range(0, COLUMN_COUNT - reduced_range):
        for row in range(0, ROW_COUNT):
            list_results = []
            for idx in list_idx_offsets:
                list_results.append(board[row][col + idx])
            # If the list is identical and the player is in the list, then increment counter
            if list_els_identical(list_results) and player_color in list_results:
                counter += 1
    # Checks columns
    for col in range(0, COLUMN_COUNT):
        for row in range(0, ROW_COUNT - reduced_range):
            list_results = []
            for idx in list_idx_offsets:
                list_results.append(board[row + idx][col])
            if list_els_identical(list_results) and player_color in list_results:
                counter += 1
    # Check diagonals positive
    for col in range(0, COLUMN_COUNT - reduced_range):
        for row in range(0, ROW_COUNT - reduced_range):
            list_results = []
            for idx in list_idx_offsets:
                list_results.append(board[row + idx][col + idx])
            if list_els_identical(list_results) and player_color in list_results:
                counter += 1
    # Check diagonals negative
    for col in range(0, COLUMN_COUNT - reduced_range):
        for row in range(reduced_range, ROW_COUNT):
            list_results = []
            for idx in list_idx_offsets:
                list_results.append(board[row - idx][col + idx])
            if list_els_identical(list_results) and player_color in list_results:
                counter += 1
    return counter

Answer 1

• Пройдите по полю один раз (по рангу или по файлам)

  • Для каждого поля проверьте наличие полос (глядя на смежное поле; если оно имеет тот же символ, то поле за ним в том же направлении и т. Д.), Но только «вперед»: в половине направлений, а именно те, где поля, которые вы еще не прошли, лежат.
    Например. при ходьбе по званию это будет:

    **********
    ****X-----
    .../|\....
    ../.|.\...
    ./..|..\..
    

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

Answer 2

Если есть только х много фигур, проверьте только х много в серии, так как не может быть больше, затем остановитесь. Это будет быстрее, чем проверка каждой комбинации.