时间戳

首页 > 解决方案 > 如何更有效地检查游戏板上的条纹？

python - 如何更有效地检查游戏板上的条纹？

问题描述

下面的函数像这样接收一个二维数组。

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

该函数的目的是计算我的二维数组中存在的指定大小的“条纹”的数量。条纹被定义为以水平、垂直或对角线排列的连续标记线。

以下示例计为 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

标签： pythonalgorithmperformance

解决方案

  • 实地考察一次（按等级或按文件）

    • 对于每个字段，检查是否有条纹（通过查看相邻字段；如果它具有相同的符号，则在相同方向上超出它的字段等）但仅“向前”：在一半方向上，即您拥有字段的方向还没走过去还躺着。
      例如，当按行列行走时，这将是：

      **********
****X-----
.../|\....
../.|.\...
./..|..\..
  • 将任何发现的条纹保存到结果中
  • 为每个字段创建一个标志矩阵，表示您已经从该字段中查找了这四个方向中的哪些方向
  • 从字段中查找条纹时，对于您查看的具有相同符号的每个字段，适当地填充上述标志（对于当前单元格，也以相同的方式填充标志）。当最终走过那个领域时，不要再看那些方向。
    • 这将保证您在结果中只有完整的条纹，而不是它们的部分。
  • 最后，所有字段都将设置所有标志。您可以将此作为调试断言进行检查（如果未设置所有标志，则您无法从相应字段中检查相应方向）。

推荐阅读