cpp 解法, 执行用时: 152 ms, 内存消耗: 22.1 MB, 提交时间: 2023-10-27 22:36:20
using PII = pair<int,int>;
using PLL = pair<long,long>;
constexpr PII dirs[4]={{0,1}, {1,0}, {1,1}, {1,-1}};
int ptr_uf[10000], cnt_uf[10000];
void init_uf(int n){
for(int i=0; i<n; ++i){
ptr_uf[i] = i;
cnt_uf[i] = 1;
}
}
int find_uf(int i){
return i==ptr_uf[i]?i:(ptr_uf[i]=find_uf(ptr_uf[i]));
}
void add_uf(int i, int j){
i = find_uf(i);
j = find_uf(j);
if(i!=j){
cnt_uf[i] += cnt_uf[j];
cnt_uf[j] = 0;
ptr_uf[j] = i;
}
}
inline long codec(int x, int y, int color){
constexpr int W = 31;
constexpr long D = 1e9+10;
return ((((x+D)<<W)|(y+D))<<1)|color;
}
inline tuple<int,int,int> decode(long c){
constexpr long W = 31, M = (1L<<W)-1;
constexpr long D = 1e9+10;
return {((c>>(W+1))&M)-D, ((c>>1)&M)-D, c&1};
}
class Solution {
unordered_set<long> piece_set;
unordered_set<long> check_one_step(vector<vector<int>>& pieces, int color){
int other_color = 1-color;
unordered_set<long> win_steps;
for(auto &p:pieces){
if(p[2]==color){
int x0 = p[0], y0 = p[1];
for(auto [dx, dy]:dirs){
for(int d=0; d<5; ++d){
int x1 = x0-d*dx, y1 = y0-d*dy, n1=0, n2=0, x2, y2;
for(int x=x1, y=y1, k=0; k<5; ++k, x+=dx, y+=dy){
if(piece_set.count(codec(x,y,color))){
++n1;
} else if(piece_set.count(codec(x,y,other_color))){
++n2;
} else {
x2 = x, y2 = y;
}
}
if(n1==4 and n2==0){
win_steps.insert(codec(x2, y2, color));
}
}
}
}
}
return win_steps;
}
bool check_two_step(vector<vector<int>>& pieces, int color){
int other_color = 1-color;
vector<PLL> win_steps;
unordered_set<long> pts;
long buf[10];
for(auto &p:pieces){
if(p[2]==color){
int x0 = p[0], y0 = p[1];
for(auto [dx, dy]:dirs){
for(int d=0; d<5; ++d){
int x1 = x0-d*dx, y1 = y0-d*dy, n1=0, n2=0, l=0;
for(int x=x1, y=y1, k=0; k<5; ++k, x+=dx, y+=dy){
if(piece_set.count(codec(x,y,color))){
++n1;
} else if(piece_set.count(codec(x,y,other_color))){
++n2;
} else {
buf[l++] = codec(x, y, color);
}
}
if(n1==3 and n2==0){
win_steps.emplace_back(buf[0], buf[1]);
pts.insert(buf[0]);
pts.insert(buf[1]);
}
}
}
}
}
unordered_map<long,int> pt_ids;
for(auto p:pts){
int i = pt_ids.size();
pt_ids[p] = i;
}
init_uf(pt_ids.size());
for(auto [p1, p2]:win_steps){
int i1=pt_ids[p1], i2=pt_ids[p2];
add_uf(i1, i2);
}
for(int i=0, n=pt_ids.size(); i<n; ++i){
if(cnt_uf[i]>=3){
return true;
}
}
return false;
}
public:
string gobang(vector<vector<int>>& pieces) {
for(auto &p:pieces){
piece_set.insert(codec(p[0], p[1], p[2]));
}
auto black_one_steps = check_one_step(pieces, 0);
auto white_one_steps = check_one_step(pieces, 1);
if(black_one_steps.size()>=1){
return "Black";
} else if(white_one_steps.size()>=2){
return "White";
} else if(white_one_steps.size()>=1){
// 黑棋堵住白棋必胜步
auto [black_x0, black_y0, black_c0] = decode(*white_one_steps.begin());
pieces.push_back({black_x0, black_y0, 0});
piece_set.insert(codec(black_x0, black_y0, 0));
auto black_steps_v2 = check_one_step(pieces, 0);
if(black_steps_v2.size()>=2){
return "Black";
} else {
return "None";
}
} else if(check_two_step(pieces, 0)){
return "Black";
} else {
return "None";
}
}
};
java 解法, 执行用时: 63 ms, 内存消耗: 44.7 MB, 提交时间: 2023-10-27 22:35:29
class Solution {
public String gobang(int[][] pieces) {
Map<Long, List<Long>> rows = new HashMap<>();
Map<Long, List<Long>> cols = new HashMap<>();
Map<Long, List<Long>> cls = new HashMap<>();
Map<Long, List<Long>> crs = new HashMap<>();
// true:black false:white
Map<Long, Integer> cm = new HashMap<>();
for (int[] p : pieces) {
long r = p[0];
long c = p[1];
long pos = offset(r, c);
cm.put(pos, p[2]);
// row
rows.computeIfAbsent(r, z -> new ArrayList<>()).add(c);
cols.computeIfAbsent(c, z -> new ArrayList<>()).add(r);
cls.computeIfAbsent(r + c, z -> new ArrayList<>()).add(r);
crs.computeIfAbsent(r - c, z -> new ArrayList<>()).add(r);
}
// S1:寻找黑方制胜点
// am,key 在某处落子，会使得生成line
Map<Long, Set<Line>> black4Map = new HashMap<>();
Map<Long, Set<Line>> black3Map = new HashMap<>();
Map<Long, Set<Line>> white4Map = new HashMap<>();
for (int i = 0; i < 4; i++) {
Map<Long, List<Long>> m = null;
if (i == 0) m = rows;
if (i == 1) m = cols;
if (i == 2) m = cls;
if (i == 3) m = crs;
for (Long v : m.keySet()) {
List<Long> pl = m.get(v);
int size = pl.size();
if (size < 3) {
continue;
}
Collections.sort(pl);
for (int idx = 0; idx < size; idx++) {
long pos = pl.get(idx);
long[] r = new long[8];
long[] c = new long[8];
int[] colors = new int[8];
int[] cc = new int[3];
for (int k = 0; k < 7; k++) {
if (i == 0) {
r[k] = v;
c[k] = pos - 2 + k;
} else if (i == 1) {
r[k] = pos - 2 + k;
c[k] = v;
} else if (i == 2) {
r[k] = pos - 2 + k;
c[k] = v - r[k];
} else {
r[k] = pos - 2 + k;
c[k] = r[k] - v;
}
// -1 means blank
colors[k] = cm.getOrDefault(offset(r[k], c[k]), 2);
cc[colors[k]]++;
if (k >= 5) {
cc[colors[k - 5]]--;
}
if (k >= 4) {
int bc = cc[2];
Map<Long, Set<Line>> setMap = colors[2] == 0 ? black4Map : white4Map;
int th = cc[colors[2]];
int oc = 5 - bc - th;
if (oc != 0 || th < 3) {
// 存在他色或自色不够
continue;
}
if (th == 4) {
// 四个相同色
for (int z = k - 4; z <= k; z++) {
if (colors[z] == 2) {
setMap.computeIfAbsent(offset(r[z], c[z]), g -> new HashSet<>())
.add(new Line(offset(r[k - 4], c[k - 4]), offset(r[k], c[k]), 0));
break;
}
}
} else if (colors[2] == 0) {
// 三个相同色
int o1 = -1;
int o2 = -1;
for (int z = k - 4; z <= k; z++) {
if (colors[z] == 2) {
if (o1 == -1) {
o1 = z;
} else if (o2 == -1) {
o2 = z;
}
}
}
black3Map.computeIfAbsent(offset(r[o1], c[o1]), g -> new HashSet<>())
.add(new Line(offset(r[k - 4], c[k - 4]), offset(r[k], c[k]), offset(r[o2], c[o2])));
black3Map.computeIfAbsent(offset(r[o2], c[o2]), g -> new HashSet<>())
.add(new Line(offset(r[k - 4], c[k - 4]), offset(r[k], c[k]), offset(r[o1], c[o1])));
}
}
}
}
}
}
if (!black4Map.isEmpty()) {
return "Black";
}
if (white4Map.size() > 1) {
return "White";
}
if (white4Map.size() == 1) {
// 黑色第一落点
long pos = new ArrayList<>(white4Map.keySet()).get(0);
// 黑子落下后，是否形成多个4连
Set<Line> ls = black3Map.get(pos);
if (null == ls || ls.size() < 2) {
return "None";
} else {
return "Black";
}
}
// 白色无限制
for (long sel : black3Map.keySet()) {
Set<Line> ss = black3Map.get(sel);
if (ss.size() < 2) {
continue;
}
Set<Long> np = new HashSet<>();
for (Line l : ss) {
np.add(l.leak);
}
if (np.size() > 1) {
return "Black";
}
}
return "None";
}
long offset(long row, long col) {
return (row << 30) + col;
}
}
class Line {
long s;
long e;
long leak;
public Line(long s, long e, long leak) {
this.s = s;
this.e = e;
this.leak = leak;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Line line = (Line) o;
return s == line.s &&
e == line.e;
}
@Override
public String toString() {
return "Line{" +
"s=" + s +
", e=" + e +
", leak=" + leak +
'}';
}
@Override
public int hashCode() {
return Objects.hash(s, e);
}
}
java 解法, 执行用时: 133 ms, 内存消耗: 46.3 MB, 提交时间: 2023-10-27 22:35:13
class Solution {
public String gobang(int[][] pieces) {
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
for (int[] piece : pieces) {
map.putIfAbsent(piece[0], new HashMap<>());
map.get(piece[0]).put(piece[1], piece[2]);
}
if (howManyWins(map, 0).size() > 0) return "Black";
Set<String> whiteWins = howManyWins(map, 1);
if (whiteWins.size() > 0) {
if (whiteWins.size() > 1) return "White";
int[] onlyPosition = new int[2];
for (String s : whiteWins) {
onlyPosition[0] = Integer.parseInt(s.split(";")[0]);
onlyPosition[1] = Integer.parseInt(s.split(";")[1]);
}
if (check(map, onlyPosition[0], onlyPosition[1]).size() > 1) return "Black";
else return "None";
}
Set<String> emptyPositions = threeInFive(map);
for (String p : emptyPositions) {
int p0 = Integer.parseInt(p.split(";")[0]);
int p1 = Integer.parseInt(p.split(";")[1]);
if (check(map, p0, p1).size() > 1) return "Black";
}
return "None";
}
public Set<String> threeInFive(Map<Integer, Map<Integer, Integer>> map) {
Set<String> set = new HashSet<>();
for (Integer x : map.keySet()) {
for (Integer y : map.get(x).keySet()) {
if (map.get(x).get(y) == 0) {
for (int[] dir : dirs) {
List<Integer> left = new ArrayList<>();
int step = 1;
while (step <= 4) {
int nx = x + dir[0] * step;
int ny = y + dir[1] * step;
if (!map.containsKey(nx)) {
if (left.size() > 1) break;
left.add(step);
} else if (!map.get(nx).containsKey(ny)) {
if (left.size() > 1) break;
left.add(step);
} else if (map.get(nx).get(ny) != 0) break;
step++;
}
if (step != 5) continue;
for (int l : left) {
set.add((x + dir[0] * l) + ";" + (y + dir[1] * l));
}
}
}
}
}
return set;
}
int[][] dirs =
new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
public Set<String> check(Map<Integer, Map<Integer, Integer>> map, int x, int y) {
Set<String> set = new HashSet<>();
for (int[] dir : dirs) {
for (int i = 0; i < 5; ++i) {
int j = 0;
int left = -10;
for (j = 0; j < 5; ++j) {
if (i == j) continue;
int xPos = x + dir[0] * (i - j);
int yPos = y + dir[1] * (i - j);
if (!map.containsKey(xPos)) {
if (left != -10) break;
left = i - j;
} else if (!map.get(xPos).containsKey(yPos)) {
if (left != -10) break;
left = i - j;
} else if (map.get(xPos).get(yPos) != 0) break;
}
if (j != 5) continue;
if (left != -10) {
String s = (x + dir[0] * left) + ";" + (y + dir[1] * left);
set.add(s);
}
}
}
return set;
}
public Set<String> howManyWins(Map<Integer, Map<Integer, Integer>> map, int color) {
Set<String> set = new HashSet<>();
for (Integer x : map.keySet()) {
for (Integer y : map.get(x).keySet()) {
if (map.get(x).get(y) == color) {
for (int[] dir : dirs) {
int step = 1;
int left = 0;
while (step <= 4) {
int nx = x + dir[0] * step;
int ny = y + dir[1] * step;
if (!map.containsKey(nx)) {
if (left != 0) break;
left = step;
} else if (!map.get(nx).containsKey(ny)) {
if (left != 0) break;
left = step;
} else if (map.get(nx).get(ny) != color) break;
step++;
}
if (step != 5) continue;
String s = (x + dir[0] * left) + ";" + (y + dir[1] * left);
set.add(s);
}
}
}
}
return set;
}
}
python3 解法, 执行用时: 236 ms, 内存消耗: 19.1 MB, 提交时间: 2023-10-27 22:34:33
from sortedcontainers import SortedList
class Solution:
def gobang(self, pieces: List[List[int]]) -> str:
B = [defaultdict(SortedList) for _ in range(4)] # 黑棋的四类直线：水平, 垂直, 斜率为1, 斜率为-1
W = [defaultdict(SortedList) for _ in range(4)] # 白棋的四类直线：水平, 垂直, 斜率为1, 斜率为-1
def add_piece(x, y, c):
P = W if c else B
P[0][y].add(x)
P[1][x].add(y)
P[2][y - x].add(x)
P[3][y + x].add(x)
def get_pos(k, v, d):
if d == 0: x, y = v, k
elif d == 1: x, y = k, v
elif d == 2: x, y = v, k + v
elif d == 3: x, y = v, k - v
return (x, y)
# 找到P的棋子中，冲np(3或4)的点（填上这个点就必胜，并且没有Q的棋子阻挡）
def find_win_ps(P, Q, np) -> defaultdict(set):
win_points = defaultdict(set)
for d in range(4):
for k in P[d]:
ps, n = P[d][k], len(P[d][k])
if n < np: continue
for i in range(n + 1 - np):
dif = ps[i + np - 1] - ps[i]
if dif < 5: # <5 说明能成5
# 找出空缺的v。找规律发现在[ps[i]-(4-dif), ps[i] + 5]，不是已有的v的点
vs = [v for v in range(ps[i] + dif - 4, ps[i] + 5) if
v not in ps[i:i + np] and not has_piece(Q, (k, v, d))]
nvs = len(vs)
if nvs < 5 - np: continue # 3->2, 4->1
dt = 4 - np
for j in range(nvs - dt):
v1, v2 = vs[j], vs[j + dt]
if v2 - v1 > 4: continue
xy1, xy2 = get_pos(k, v1, d), get_pos(k, v2, d)
win_points[xy1].add(xy2)
win_points[xy2].add(xy1)
if np == 4 and len(win_points) > 1: return win_points
return win_points
def has_piece(X, kvd) -> bool:
k, v, d = kvd
return k in X[d] and v in X[d][k]
# 开始，棋子先存好
for x, y, c in pieces:
add_piece(x, y, c)
# 1. 黑先手有4连黑子，并且有空位放下能成5连黑子，就黑胜
if len(find_win_ps(B, W, 4)) > 0:
return 'Black'
# 白如果有多个冲4就赢
live_w4 = find_win_ps(W, B, 4)
if len(live_w4) > 1:
return 'White'
# 白只有1个冲4，黑先堵上；如果黑有多个冲4就赢，否则None
if len(live_w4) == 1:
x, y = list(live_w4.keys())[0]
add_piece(x, y, 0)
return 'Black' if len(find_win_ps(B, W, 4)) > 1 else 'None'
# 检查最开始如果有形成双4的点，就黑赢
return 'Black' if any(len(ds) > 1 for ds in find_win_ps(B, W, 3).values()) else 'None'
python3 解法, 执行用时: 416 ms, 内存消耗: 19.8 MB, 提交时间: 2023-10-27 22:34:01
class Solution:
def gobang(self, pieces: List[List[int]]) -> str:
D = [(1, 0), (0, 1), (1, 1), (-1, 1)]
board = {(x,y):c for x, y, c in pieces}
# 枚举指定颜色棋子五子连线的所有方案（当前棋盘额外最多下两子）
def findLines(color) :
lines = DefaultDict(list)
for x, y, c in pieces : # 枚举棋盘上所有指定颜色棋子的位置
if c != color : continue
for i, (dx, dy) in enumerate(D) : # 连线有四个方向
for k in range(3) : # 因为最多额外下两子，连线端点偏离已有棋子不超过2
nx, ny = x-dx*k, y-dy*k
head = (nx, ny, i)
if head in lines : continue # 该“端点&方向”已存在
for _ in range(5) : # 把该连线上剩下的落子位找到
c = board.get((nx, ny), -1)
if c != color :
if c >= 0 or len(lines[head]) >= 2 : # 该连线上有异色棋子，或空位过多，舍弃
lines[head].clear()
break
lines[head].append((nx, ny))
nx, ny = nx+dx, ny+dy
# 按待落子数归类连线方案
res = [[] for _ in range(3)]
for v in lines.values() :
if len(v) : res[len(v)].append(v)
return res
# 若黑棋存在一步致胜的方案，则黑胜
black = findLines(0)
if len(black[1]) > 0 : return "Black"
white = findLines(1)
positions = set(line[0] for line in white[1]) # 不同的连线可能包含相同的落子位，须去重
# 若白棋存在多个一步制胜的落子位，则白胜
if len(positions) > 1 : return "White"
if len(positions) == 1 :
# 若白棋存在一个一步制胜的落子位，则黑先手必须堵这个位置
x, y = positions.pop()
pieces.append([x, y, 0])
board[(x, y)] = 0
black = findLines(0)
# 黑棋堵位后，黑棋存在多个一步制胜的落子位，则黑剩，否则平
positions = set(line[0] for line in black[1])
return "Black" if len(positions) > 1 else "None"
# 若白棋不存在一步制胜的落子位，黑须落一子创造多于一个一步制胜的落子位才能在两步内获胜
pairs = set((pair[0], pair[1]) for pair in black[2]) # 不同的连线可能包含相同的两个落子位，须去重
positions = set()
for p1, p2 in pairs :
# 若某个落子位在之前落子对中已出现，下该位置能产生两个一步致胜的位置
if p1 in positions or p2 in positions : return "Black"
positions.add(p1)
positions.add(p2)
return "None"
golang 解法, 执行用时: 324 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-27 22:33:38
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
}
{:width="300px"}