python 消消乐算法实现

叶子陪你玩

发布于 2022-05-22 15:05:26

1.1K0

发布于 2022-05-22 15:05:26

文章被收录于专栏：叶子陪你玩编程

消消乐游戏主要是点击一个块，会将其周围的元素消除。

核心就是判断一个连通区域是否是同一个元素，如果大于等于3，就消除。

比如下面这两种就可以消除：

算法原理

这里用广度优先算法就可以，从一个起点开始，查看其上下左右的点，如果有一样的，加入待访问列表中；

然后从访问列表中拿出第一个点继续重复上面操作，直到待访问列表为空为止。

伪代码算法：

创建一个列表all_points = [] 保存连通的点
创建search_queue = [start_point] 保存待访问点
创建visted_queue = []保存访问过点
获取点击的点 point
直到search_queue为空
    获取 search_queue中的第一个点 point
    添加 point 到all_points 中，表示已访问过
    获取 point 四周围的点,保存到points变量中
    遍历points中的点
      如果该点没访问过
        将其添加到 search_queue 队列中

python代码实现：

import numpy as np
# 找到当前位置一样的所有相邻点
def find_neighbor_point(point,array):
    points = []
    px = [-1, 0, 1, 0]  # 通过px 和 py数组来实现左下右上的移动顺序
    py = [0, -1, 0, 1]

    row = point[0]
    col = point[1]

    # 遍历4个方向
    for i in range(4):
        new_row = row + px[i]
        new_col = col + py[i]
        if new_row >= 0 and new_row < 4 and new_col >= 0 and new_col < 4 and array[new_row][new_col] == array[row][col]:
            points.append((new_row,new_col))
    return points
    
if __name__ == '__main__':
    array = np.array([1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0])
    array = array.reshape(4, 4)
    array[2,0]=1
    array[0,3]=1
    array[1,3]=1
    print(array)


    start_point = (0, 3)
    print('点击位置',start_point)
    all_points = []
    search_queue = []
    visted_queue = []
    search_queue.append(start_point)
    
    while search_queue:
        point = search_queue.pop(0)
        visted_queue.append(point)
        all_points.append(point)
        points = find_neighbor_point(point,array)
        for p in points:
            if p not in visted_queue:
                search_queue.append(p)
    print('连通的点',all_points)

运行结果：