TYS的博客

算法小白努力学习中

0%

2021秋季lccup战队赛

发表于 更新于

image-20210929231014229.png

比赛的时候是用C++写的，也是按照这个思路，按照行、列、主对角线、次对角线进行分类。这样可以将二维的坐标压缩到一维进行判断，且行，列，对角线的判断方法完全相同。

判断黑棋第一步赢，与白棋第二步赢比较简单。

  • 黑棋第一步赢，则放入后黑棋后，连起来为五个黑子。这样的位置大于等于一个即可
  • 白棋第二步赢，则首先不存在黑棋一步赢的情况，放入白棋后连续白子超过五个，这样的位置需要大于等于两个，因为黑棋第一步可以堵入一个位置。

判断黑棋第三步赢，则相对复杂些

  • 如果白棋存在五连的情况，第一步首先要填入白棋的位置，然后按照黑棋一步赢的情况查找可行位置，不过这种位置需要大于等于两个
  • 填入某个黑色棋子后，可以五连的位置大于等于两个，采用defaultdict(set)来记录某个位置对应可行位置的集合
  • 如果是三或四个棋子，则坐标的max - min一定要小于等于4，这几个棋子才有可能五连。然后枚举所有可行的最小的位置(区间[max - 4, min])，并定义为start，查找不在[start, start + 4]的空位置，按棋子个数为3，4分情况讨论。

比赛时候没有想到上述做法，而是直接进行枚举所有三个，四个棋子的情况。三个棋子时有$C_5^3$共10种情况，代码写的很长，还漏了边界case。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution:
    def gobang(self, pieces: List[List[int]]) -> str:
        black = [defaultdict(set) for _ in range(4)]
        white = [defaultdict(set) for _ in range(4)]
        # 行、列、主对角线，次对角线
        def add_pieces(x, y, c):
            p = black
            if c == 1:
                p = white
            p[0][x].add(y)
            p[1][y].add(x)
            p[2][x - y].add(y)
            p[3][x + y].add(y)
        
        def get_pos(x, y, k):
            if k == 0:
                return x, y
            elif k == 1:
                return y, x
            elif k == 2:
                return x + y, y
            else:
                return x - y, y

        
        def find_pos(p, q, space):
            pos = defaultdict(set)
            for k in range(4):
                for idx, se in p[k].items():
                    vec = sorted(list(se))
                    for i in range(len(vec) - space + 1):
                        start, end = vec[i], vec[i + space - 1]
                        if end - start > 4:
                            continue
                        # s为所有可能五连的起点
                        for s in range(end - 4, start + 1):
                            arr = [v for v in range(s, s + 5) if v not in vec[i:i + space] and v not in q[k][idx]]
                            if len(arr) == 2 and space == 3:
                                x1, y1 = get_pos(idx, arr[0], k)
                                x2, y2 = get_pos(idx, arr[1], k)
                                pos[(x1, y1)].add((x2, y2))
                                pos[(x2, y2)].add((x1, y1))
                            if len(arr) == 1 and space == 4:
                                x, y = get_pos(idx, arr[0], k)
                                pos[(x, y)].add((x, y))
            return pos

        for x, y, c in pieces:
            add_pieces(x, y, c)
        # 黑棋第一步赢，则可放入位置大于等于1
        b1_pos = find_pos(black, white, 4)
        if len(b1_pos) >= 1:
            return 'Black'
        # 白棋第二步赢，则可放入位置大于1
        w2_pos = find_pos(white, black, 4)
        if len(w2_pos) > 1:
            return 'White'
        # 白棋如果存在可赢的位置，则需要填入黑棋
        if len(w2_pos) == 1:
            for x, y in w2_pos.keys():
                add_pieces(x, y, 0)
            b3_pos = find_pos(black, white, 4)
            if len(b3_pos) > 1:
                return 'Black'
        else:
            b3_pos = find_pos(black, white, 3)
            for p, cnt in b3_pos.items():
                if len(cnt) >= 2:
                    print(p, cnt)
                    return 'Black'

        return 'None'