刷题笔记合集🔗

五子棋迷

问题描述

小基 和小柯是五子棋迷，工作之余经常切磋棋艺。这不，这会儿又下起来了。走了一会儿，轮 小基 了，对着一条线思考起来了，这条线上的棋子分布如下:
用数组表示: -1 0 1 1 1 0 1 0 1 -1
棋了分布说明:

• -1 代表白子，0 代表空位，1 代表黑子
• 数组长度 ，满足 ， 为奇数

你得帮他写一个程序，算出最有利的出子位置。最有利定义：

• 找到一个空位(0)，用棋子(1/-1)填充该位置，可以使得当前子的最大连续长度变大
• 如果存在多个位置，返回最靠近中间的较小的那个坐标
• 如果不存在可行位置，直接返回 -1
• 连续长度不能超过 5 个(五子棋约束)

输入格式

第一行: 当前出子颜色

第二行: 当前的棋局状态

输出格式

1 个整数，表示出子位置的数组下标

样例输入

1
-1 0 1 1 1 0 1 -1 1

-1
-1 0 1 1 1 0 1 0 1 -1 1

1
0 0 0 0 1 0 0 0 0 1 0

样例输出

5

1

5

数据范围

• 
• 为奇数
• 数组元素只包含 -1, 0, 1

题解

这道题是一个关于五子棋的问题，我们需要找到一个最有利的落子位置，使当前颜色棋子的最大连续长度增加。

首先分析题目要求：

1. 找到一个空位(0)，放置当前颜色的棋子，使得当前颜色棋子的最大连续长度变大
2. 如果有多个可选位置，选择最靠近中间且索引值较小的位置
3. 如果没有可行位置，返回-1
4. 连续长度不能超过5个

这是一个搜索问题，我们可以使用"滑动窗口"或"双指针"的思路来解决。基本思路如下：

1. 首先计算出当前棋盘上，指定颜色棋子的最大连续长度
2. 尝试在每一个空位(0)放置当前颜色的棋子，然后计算新的最大连续长度
3. 如果新的最大连续长度大于原始最大连续长度，且不超过5，则该位置是一个候选位置
4. 在所有候选位置中，选择最靠近中间且索引较小的位置作为结果

具体实现中，我们用两个指针L和R来表示一个连续区间，这个区间内必须且只能包含一个空位用于落子，其它棋子必须是当前的颜色。当区间内包含的棋子数量不符合要求时，我们需要移动L或R指针来找到新的合法区间。

算法的时间复杂度为O(n)，其中n是棋盘的长度。这是因为我们使用双指针遍历棋盘，每个位置最多被访问常数次。空间复杂度为O(1)，只使用了常数额外空间。

对于题目给出的数据范围(棋盘最长不超过40)，这个算法的效率是足够的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
color = int(input())  # 当前出子颜色
board = list(map(int, input().split()))  # 当前棋局状态

def get_init_max_len(color, board):
    """计算当前颜色棋子的最大连续长度"""
    max_len = 0
    curr_len = 0
    
    for piece in board:
        if piece == color:
            curr_len += 1
            max_len = max(max_len, curr_len)
        else:
            curr_len = 0
            
    return max_len

def get_best_position(color, board):
    # 获取初始最大连续长度
    init_max_len = get_init_max_len(color, board)
    
    # 棋盘中间位置
    mid = len(board) // 2
    
    # 存储所有候选位置和对应的连续长度
    candidates = []
    
    # 双指针遍历
    left = 0
    right = 0
    
    # 空位数量和位置
    zeros = 0
    pos = -1
    
    while right < len(board):
        # 当前位置是空位
        if board[right] == 0:
            zeros += 1
            
            # 如果空位数量超过1，检查left到right-1是否形成一个连棋
            if zeros > 1 and right - left <= 5 and right - left > init_max_len:
                candidates.append((pos, right - left))
            
            # 如果空位超过1个，需要将左指针移到上一个空位的右边
            if zeros > 1:
                zeros -= 1
                left = pos + 1
            
            # 更新空位位置
            pos = right
            
            right += 1
        # 当前位置是其他颜色棋子，连棋中断
        elif board[right] != color:
            # 检查left到right-1是否已经落过子且形成连棋
            if zeros == 1 and right - left <= 5 and right - left > init_max_len:
                candidates.append((pos, right - left))
            
            # 重置状态
            pos = -1
            zeros = 0
            left = right + 1
            right += 1
        # 当前位置是当前颜色棋子，连棋继续
        else:
            right += 1
    
    # 处理最后一段
    if zeros == 1 and right - left <= 5 and right - left > init_max_len:
        candidates.append((pos, right - left))
    
    # 如果没有候选位置，返回-1
    if not candidates:
        return -1
    
    # 按照连棋长度降序排序，长度相同时按照距离中间的距离升序，距离相同时按照位置升序
    candidates.sort(key=lambda x: (-x[1], abs(x[0] - mid), x[0]))
    
    return candidates[0][0]

# 输出结果
print(get_best_position(color, board))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 计算当前颜色棋子的最大连续长度
int getInitMaxLen(int color, vector<int>& board) {
    int maxLen = 0;
    int currLen = 0;
    
    for (int piece : board) {
        if (piece == color) {
            currLen++;
            maxLen = max(maxLen, currLen);
        } else {
            currLen = 0;
        }
    }
    
    return maxLen;
}

// 比较两个位置的优先级
bool compareCandidates(const pair<int, int>& a, const pair<int, int>& b, int mid) {
    // 先按连续长度降序
    if (a.second != b.second) {
        return a.second > b.second;
    }
    
    // 如果长度相同，按照距离中间的距离升序
    int distA = abs(a.first - mid);
    int distB = abs(b.first - mid);
    
    if (distA != distB) {
        return distA < distB;
    }
    
    // 如果距离也相同，按照位置升序
    return a.first < b.first;
}

int getBestPosition(int color, vector<i