本文共 5255 字，大约阅读时间需要 17 分钟。

要解决这个问题，我们需要判断在当前的4x4井字棋局面下，轮到X下棋时，是否存在一个强制性胜利的位置。如果存在，找出第一个这样的位置；否则，返回“#####”。

方法思路

解决代码

import sys
from functools import lru_cache
def 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 += 1
def 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 False
def 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 False
def 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 += 1
if __name__ == "__main__":
    main()

代码解释

转载地址：http://udxfk.baihongyu.com/