本文共 5104 字，大约阅读时间需要 17 分钟。
要解决这个问题，我们需要判断在当前的4x4井字棋局面下，轮到X下棋时，是否存在一个强制性胜利的位置。如果存在，找出第一个这样的位置；否则，返回“#####”。
import sysfrom functools import lru_cachedef main(): sys.setrecursionlimit(1000000) input = sys.stdin.read().splitlines() idx = 0 while idx < len(input): if input[idx].startswith('?'): idx += 1 board = [] for _ in range(4): line = input[idx].strip() idx += 1 board.append(list(line)) found = False for i in range(4): for j in range(4): if board[i][j] == '.': temp_board = [row.copy() for row in board] temp_board[i][j] = 'x' if check_win(temp_board, i, j): print(f"({i},{j})") found = True break if found: break if not found: print("#####") else: idx += 1def check_win(board, x, y): count_x = 0 count_o = 0 for i in range(4): for j in range(4): if board[i][j] == 'x': count_x += 1 elif board[i][j] == 'o': count_o += 1 if count_x == 4 or count_o == 4: return True for i in range(4): count_x = 0 count_o = 0 for j in range(4): if board[i][j] == 'x': count_x += 1 elif board[i][j] == 'o': count_o += 1 if count_x == 4 or count_o == 4: return True diag1 = True count_x = 0 count_o = 0 for i in range(4): if board[i][i] == 'x': count_x += 1 elif board[i][i] == 'o': count_o += 1 if count_x == 4 or count_o == 4: diag1 = False break if diag1: return True diag2 = True count_x = 0 count_o = 0 for i in range(4): if board[i][3-i] == 'x': count_x += 1 elif board[i][3-i] == 'o': count_o += 1 if count_x == 4 or count_o == 4: diag2 = False break if diag2: return True return Falsedef solve(board): @lru_cache(maxsize=None) def dfs(x, y, is_x_turn): if check_win(board, x, y): return True if is_x_turn: for i in range(4): for j in range(4): if board[i][j] == '.': temp = board[i][j] board[i][j] = 'x' if not dfs(i, j, False): board[i][j] = temp return False board[i][j] = temp if not dfs(i, j, False): return True board[i][j] = temp return False return False else: for i in range(4): for j in range(4): if board[i][j] == '.': temp = board[i][j] board[i][j] = 'o' if not dfs(i, j, True): board[i][j] = temp return False board[i][j] = temp if not dfs(i, j, True): return True board[i][j] = temp return False return False for i in range(4): for j in range(4): if board[i][j] == '.': temp_board = [row.copy() for row in board] temp_board[i][j] = 'x' if dfs(i, j, False): return True temp_board[i][j] = '.' return Falsedef main(): sys.setrecursionlimit(1000000) input = sys.stdin.read().splitlines() idx = 0 while idx < len(input): if input[idx].startswith('?'): idx += 1 board = [] for _ in range(4): line = input[idx].strip() idx += 1 board.append(list(line)) found = False for i in range(4): for j in range(4): if board[i][j] == '.': temp_board = [row.copy() for row in board] temp_board[i][j] = 'x' if solve(temp_board): print(f"({i},{j})") found = True break if found: break if not found: print("#####") else: idx += 1if __name__ == "__main__": main() 转载地址：http://udxfk.baihongyu.com/