蓝桥杯python连连看

### 蓝桥杯 Python 编程竞赛连连看题目解析

#### 题目描述
在一个 n×m 的棋盘上玩连连看游戏。给定一个初始状态的棋盘，其中每个格子可能为空白或者是某种颜色的小球。玩家可以选择两个相同颜色且中间无障碍物阻挡的小球消除它们。如果一次操作可以消去一对小球，则得一分；否则不得分。

目标是在有限步数内获得最高分数并清空整个棋盘。对于任意给出的状态，请计算最多能得多少分以及对应的最优解法路径[^1]。

#### 解题思路
此问题属于图论中的最短路径算法应用之一。可以通过广度优先搜索(BFS)来解决这个问题：

- **预处理阶段**
- 将输入数据转换成二维列表表示棋盘布局。
- 使用字典记录每种颜色的位置集合以便快速查找匹配项。

- **核心逻辑实现**
- 对于每一个未被访问过的节点(即非空白位置)，尝试找到与其相连通的所有同色节点形成链表结构。
- 如果该链条长度大于等于2则说明存在可移除组合，此时更新得分并将这些位置标记为已访问。
- 记录下当前状态下所能达到的最大得分及其对应的操作序列直到遍历完整个地图为止。

下面是一个简单的Python代码框架用于求解上述过程:

from collections import deque, defaultdict


def bfs(board, start_x, start_y):
    queue = deque([(start_x, start_y)])
    visited = set()
    color_group = []
    
    while queue:
        x, y = queue.popleft()

        if (x,y) not in visited and board[x][y]:
            visited.add((x, y))
            color_group.append([x, y])

            directions = [(0,-1), (-1,0), (0,+1), (+1,0)]
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < len(board) and \
                   0 <= ny < len(board[0]) and \
                   board[nx][ny]==board[start_x][start_y]:
                    queue.append((nx, ny))

    return color_group if len(color_group)>1 else []


def max_score_of_lianliankan(board):
    scores = 0
    moves = []

    colors_positions=defaultdict(list)

    # Preprocess to record positions of each color.
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j]!='.':
                colors_positions[board[i][j]].append((i,j))

    for group in colors_positions.values():
        for pos in group:
            matched=bfs(board,*pos)
            if matched:
                scores+=len(matched)//2
                moves.extend(matched)

    return scores,moves