LCP 48-无限棋局

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

小力正在通过残局练习来备战「力扣挑战赛」中的「五子棋」项目，他想请你能帮他预测当前残局的输赢情况。棋盘中的棋子分布信息记录于二维数组 pieces
中，其中 pieces[i] = [x,y,color] 表示第 i 枚棋子的横坐标为 x，纵坐标为 y，棋子颜色为 color(0
表示黑棋，1 表示白棋)。假如黑棋先行，并且黑棋和白棋都按最优策略落子，请你求出当前棋局在三步（按 黑、白、黑
的落子顺序）之内的输赢情况（三步之内先构成同行、列或对角线连续同颜色的至少 5 颗即为获胜）： - 黑棋胜, 请返回 "Black" - 白棋胜,
请返回 "White" - 仍无胜者, 请返回 "None" 注意： - 和传统的五子棋项目不同，「力扣挑战赛」中的「五子棋」项目
不存在边界限制，即可在 任意位置 落子； - 黑棋和白棋均按 3 步内的输赢情况进行最优策略的选择 - 测试数据保证所给棋局目前无胜者；
- 测试数据保证不会存在坐标一样的棋子。 示例 1： > 输入： > pieces = [[0,0,1],[1,1,1],[2,2,0]] >

输出："None" > > 解释：无论黑、白棋以何种方式落子，三步以内都不会产生胜者。 示例 2： > 输入： > pieces = [[1,2,1],[1,4,1],[1,5,1],[2,1,0],[2,3,0],[2,4,0],[3,2,1],[3,4,0],[4,2,1],[5,2,1]]

输出："Black" > > 解释：三步之内黑棋必胜，以下是一种可能的落子情况：
![902b87df29998b1c181146c8fdb3a4b6.gif](https://pic.leetcode-
cn.com/1629800639-KabOfY-902b87df29998b1c181146c8fdb3a4b6.gif){:width=”300px”}
提示： - 0 <= pieces.length <= 1000 - pieces[i].length = 3 - -10^9 <= pieces[i][0], pieces[i][1] <=10^9 - 0 <= pieces[i][2] <=1

分类讨论题：

  1. 黑第一手就可以获胜，输出 "Black"
  2. 黑第一手无法获胜
    2.1 白可以一步胜，且获胜位置不止一处，此时黑无法阻止白获胜，输出 "White"
    2.2 白可以一步胜，但获胜位置只有一处，此时黑第一手下在该处，白无法获胜，进入 3
    2.3 白无获胜位置，进入 3
  3. 白无法获胜，于是白的策略是防止黑获胜。枚举黑第一手的位置（除了 2.2 中黑只能下在一个位置），然后判断黑第二手能否有超过一处获胜位置，若有超过一处，则白无法阻止黑获胜，输出 "Black"，否则输出 "None"。

枚举位置的技巧见注释。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
const (
	black = "Black"
	white = "White"
	none  = "None"
)

type pair struct{ x, y int }
var dir8 = []pair{ {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} }

func gobang(pieces [][]int) string {
	color := make(map[pair]int, len(pieces)+1)
	for _, p := range pieces {
		p[2]++ // 为方便利用零值，将黑改为 1，白改为 2
		color[pair{p[0], p[1]}] = p[2]
	}

	// 在 (i,j) 落子，颜色为 c，判断落子的一方是否获胜
	checkWin := func(i, j, c int) bool {
		for k, d := range dir8[:4] {
			cnt := 1
			// 检查一个方向
			for x, y := i+d.x, j+d.y; color[pair{x, y}] == c; x, y = x+d.x, y+d.y {
				cnt++
			}
			// 检查相反的另一方向
			d = dir8[k^4]
			for x, y := i+d.x, j+d.y; color[pair{x, y}] == c; x, y = x+d.x, y+d.y {
				cnt++
			}
			if cnt >= 5 {
				return true
			}
		}
		return false
	}

	// 1. 黑第一手就可以获胜
	for _, p := range pieces {
		if p[2] == 2 {
			continue
		}
		i, j := p[0], p[1]
		for _, d := range dir8 { // 黑要想一步获胜只能下在黑子周围
			if x, y := i+d.x, j+d.y; color[pair{x, y}] == 0 && checkWin(x, y, 1) {
				return black
			}
		}
	}

	// 2. 黑第一手无法获胜
	whites := map[pair]bool{}
	posW := pair{}
	for _, p := range pieces {
		if p[2] == 1 {
			continue
		}
		i, j := p[0], p[1]
		for _, d := range dir8 { // 白要想一步获胜只能下在白子周围
			x, y := i+d.x, j+d.y
			q := pair{x, y}
			if color[q] == 0 && checkWin(x, y, 2) {
				// 2.1 白可以一步胜，且获胜位置不止一处
				if whites[q] = true; len(whites) > 1 {
					return white
				}
				posW = q
			}
		}
	}

	// 2.2 白可以一步胜，但获胜位置只有一处
	if len(whites) == 1 {
		color[posW] = 1 // 黑第一手下在该处，阻止白获胜
		blacks := map[pair]bool{}
		// 检查第三步的黑能否获胜
		checkBlackWin := func(i, j int) bool {
			for _, d := range dir8 { // 黑要获胜只能下在黑子周围
				x, y := i+d.x, j+d.y
				p := pair{x, y}
				if color[p] == 0 && checkWin(x, y, 1) {
					if blacks[p] = true; len(blacks) > 1 {
						return true
					}
				}
			}
			return false
		}
		checkBlackWin(posW.x, posW.y)
		for _, p := range pieces {
			if p[2] == 1 && checkBlackWin(p[0], p[1]) {
				return black
			}
		}
		return none
	}

	// 3. 白无法获胜，于是白的策略是防止黑获胜
	// 根据黑第一步的落子位置，在该位置周围枚举黑第三步的落子位置，检查黑能否获胜
	checkBlackWin := func(i0, j0 int) bool {
		blacks := map[pair]bool{}
		for k, d := range dir8 {
			for l, i, j := 0, i0, j0; l < 5; l++ { // 如果黑可以获胜，这两枚黑子的距离不会超过 5
				i += d.x
				j += d.y
				p := pair{i, j}
				if color[p] > 0 {
					continue
				}
				cnt := 1
				// 检查一个方向
				for x, y := i+d.x, j+d.y; color[pair{x, y}] == 1; x, y = x+d.x, y+d.y {
					cnt++
				}
				// 检查相反的另一方向
				d2 := dir8[k^4]
				for x, y := i+d2.x, j+d2.y; color[pair{x, y}] == 1; x, y = x+d2.x, y+d2.y {
					cnt++
				}
				if cnt >= 5 {
					if blacks[p] = true; len(blacks) > 1 {
						return true
					}
				}
			}
		}
		return false
	}
	vis := map[pair]bool{} // 常数优化：避免重复枚举
	for _, p := range pieces {
		if p[2] == 2 {
			continue
		}
		i, j := p[0], p[1]
		// 枚举黑第一步的落子。由于黑要下两手棋，需要枚举黑子周围两圈
		for dx := -2; dx <= 2; dx++ {
			for dy := -2; dy <= 2; dy++ {
				if dx == 0 && dy == 0 {
					continue
				}
				x, y := i+dx, j+dy
				q := pair{x, y}
				if vis[q] || color[q] > 0 {
					continue
				}
				color[q] = 1 // 黑落子
				vis[q] = true
				if checkBlackWin(x, y) {
					return black
				}
				delete(color, q)
			}
		}
	}
	return none
}
 Comments
On this page
LCP 48-无限棋局