启发式搜索与博弈树

from collections import deque

def bidirectional_bfs(graph: dict, start, end) -> list | None:
    """双向 BFS：从起点和终点同时搜索，中间相遇"""
    if start == end:
        return [start]

    # 前向搜索：从 start 出发
    front_visited = {start: None}  # node -> parent
    back_visited = {end: None}
    front_queue = deque([start])
    back_queue = deque([end])
    meeting_point = None

    while front_queue and back_queue:
        # 扩展前向一层
        for _ in range(len(front_queue)):
            node = front_queue.popleft()
            for neighbor in graph.get(node, []):
                if neighbor not in front_visited:
                    front_visited[neighbor] = node
                    front_queue.append(neighbor)
                    if neighbor in back_visited:
                        meeting_point = neighbor
                        break
            if meeting_point:
                break

        if meeting_point:
            break

        # 扩展后向一层
        for _ in range(len(back_queue)):
            node = back_queue.popleft()
            for neighbor in graph.get(node, []):
                if neighbor not in back_visited:
                    back_visited[neighbor] = node
                    back_queue.append(neighbor)
                    if neighbor in front_visited:
                        meeting_point = neighbor
                        break
            if meeting_point:
                break

    if not meeting_point:
        return None

    # 拼接路径：start -> meeting_point -> end
    # 前半段
    path = []
    cur = meeting_point
    while cur is not None:
        path.append(cur)
        cur = front_visited[cur]
    path.reverse()
    # 后半段
    cur = back_visited[meeting_point]
    while cur is not None:
        path.append(cur)
        cur = back_visited[cur]
    return path

def ladderLength(beginWord: str, endWord: str, wordList: list) -> int:
    """单词接龙：双向 BFS"""
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    front = {beginWord}
    back = {endWord}
    visited = set()
    steps = 1

    while front and back:
        # 总是扩展较小的一侧（优化）
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    if c == word[i]:
                        continue
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in back:
                        return steps + 1
                    if new_word in word_set and new_word not in visited:
                        visited.add(new_word)
                        next_front.add(new_word)
        front = next_front
        steps += 1
    return 0

def iddfs(graph: dict, start, is_goal) -> int | None:
    """迭代深化 DFS：返回目标所在深度"""
    def _dls(node, depth, visited):
        """Depth-Limited Search"""
        if is_goal(node):
            return depth
        if depth == 0:
            return None
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                result = _dls(neighbor, depth - 1, visited)
                if result is not None:
                    return result
        return None

    for depth in range(0, 100):  # 上限防无限循环
        visited = set()
        result = _dls(start, depth, visited)
        if result is not None:
            return result
    return None

import heapq

def astar(grid: list[list[int]], start: tuple, end: tuple) -> int:
    """A* 算法：在二维网格中求最短路径。0=可走, 1=障碍"""
    rows, cols = len(grid), len(grid[0])

    def manhattan(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    # 优先队列：(f, g, pos)
    open_set = [(manhattan(start, end), 0, start)]
    g_score = {start: 0}
    visited = set()

    while open_set:
        f, g, pos = heapq.heappop(open_set)
        if pos == end:
            return g
        if pos in visited:
            continue
        visited.add(pos)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = pos[0] + dx, pos[1] + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                neighbor = (nx, ny)
                new_g = g + 1
                if neighbor not in g_score or new_g < g_score[neighbor]:
                    g_score[neighbor] = new_g
                    new_f = new_g + manhattan(neighbor, end)
                    heapq.heappush(open_set, (new_f, new_g, neighbor))
    return -1  # 不可达

def eight_puzzle(start: tuple, goal: tuple) -> int:
    """八数码问题：A* + 曼哈顿距离和"""
    def h(state):
        dist = 0
        for i in range(9):
            if state[i] == 0:
                continue
            target = goal.index(state[i])
            dist += abs(i // 3 - target // 3) + abs(i % 3 - target % 3)
        return dist

    open_set = [(h(start), 0, start)]
    g_score = {start: 0}
    while open_set:
        f, g, state = heapq.heappop(open_set)
        if state == goal:
            return g
        zero = state.index(0)
        zx, zy = zero // 3, zero % 3
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = zx + dx, zy + dy
            if 0 <= nx < 3 and 0 <= ny < 3:
                new_zero = nx * 3 + ny
                lst = list(state)
                lst[zero], lst[new_zero] = lst[new_zero], lst[zero]
                new_state = tuple(lst)
                new_g = g + 1
                if new_state not in g_score or new_g < g_score[new_state]:
                    g_score[new_state] = new_g
                    heapq.heappush(open_set, (new_g + h(new_state), new_g, new_state))
    return -1

def ida_star(start, goal, h, neighbors):
    """IDA* 算法：内存受限启发式搜索"""
    def search(path, g, threshold):
        node = path[-1]
        f = g + h(node, goal)
        if f > threshold:
            return f, None
        if node == goal:
            return f, list(path)
        min_threshold = float('inf')
        for neighbor, cost in neighbors(node):
            if neighbor in path:  # 简单环检测
                continue
            path.append(neighbor)
            t, result = search(path, g + cost, threshold)
            if result is not None:
                return t, result
            if t < min_threshold:
                min_threshold = t
            path.pop()
        return min_threshold, None

    threshold = h(start, goal)
    path = [start]
    while True:
        t, result = search(path, 0, threshold)
        if result is not None:
            return result
        if t == float('inf'):
            return None  # 不可达
        threshold = t

def minimax(state, is_max_turn, terminal_value, children, depth=10):
    """Minimax 算法
    - state: 当前状态
    - is_max_turn: 当前是否为 MAX 玩家回合
    - terminal_value(state): 终局估值（None 表示非终局）
    - children(state): 返回所有合法后继状态
    - depth: 最大搜索深度
    """
    val = terminal_value(state)
    if val is not None:
        return val
    if depth == 0:
        return heuristic_eval(state)

    if is_max_turn:
        best = -float('inf')
        for child in children(state):
            best = max(best, minimax(child, False, terminal_value, children, depth - 1))
        return best
    else:
        best = float('inf')
        for child in children(state):
            best = min(best, minimax(child, True, terminal_value, children, depth - 1))
        return best

def heuristic_eval(state):
    """启发式估值函数（需根据具体博弈定义）"""
    return 0

def alphabeta(state, depth, alpha, beta, is_max_turn, terminal_value, children):
    """Alpha-Beta 剪枝"""
    val = terminal_value(state)
    if val is not None:
        return val
    if depth == 0:
        return heuristic_eval(state)

    if is_max_turn:
        best = -float('inf')
        for child in children(state):
            best = max(best, alphabeta(child, depth - 1, alpha, beta, False, terminal_value, children))
            alpha = max(alpha, best)
            if alpha >= beta:
                break  # beta 剪枝
        return best
    else:
        best = float('inf')
        for child in children(state):
            best = min(best, alphabeta(child, depth - 1, alpha, beta, True, terminal_value, children))
            beta = min(beta, best)
            if beta <= alpha:
                break  # alpha 剪枝
        return best

def negamax(state, depth, alpha, beta, color, terminal_value, children):
    """Negamax + Alpha-Beta：所有节点统一为当前玩家最大化"""
    val = terminal_value(state)
    if val is not None:
        return color * val
    if depth == 0:
        return color * heuristic_eval(state)

    best = -float('inf')
    for child in children(state):
        val = -negamax(child, depth - 1, -beta, -alpha, -color, terminal_value, children)
        best = max(best, val)
        alpha = max(alpha, best)
        if alpha >= beta:
            break
    return best

def predict_the_winner(nums: list) -> bool:
    """LeetCode 486：Minimax 判断玩家 1 是否必胜"""
    def minimax(nums, l, r, turn):
        if l == r:
            return turn * nums[l]
        pick_left = nums[l] + turn * minimax(nums, l + 1, r, -turn)
        pick_right = nums[r] + turn * minimax(nums, l, r - 1, -turn)
        return max(pick_left, pick_right) if turn == 1 else min(pick_left, pick_right)

    score = minimax(nums, 0, len(nums) - 1, 1)
    return score >= 0

import heapq

def slidingPuzzle(board: list[list[int]]) -> int:
    """2x3 滑动谜题：A* + 曼哈顿距离"""
    goal = (1, 2, 3, 4, 5, 0)
    start = tuple(board[0] + board[1])
    if start == goal:
        return 0

    def h(state):
        dist = 0
        for i in range(6):
            if state[i] == 0:
                continue
            target = state[i] - 1
            dist += abs(i // 3 - target // 3) + abs(i % 3 - target % 3)
        return dist

    # 邻居索引
    neighbors = {0: [1, 3], 1: [0, 2, 4], 2: [1, 5],
                 3: [0, 4], 4: [1, 3, 5], 5: [2, 4]}

    open_set = [(h(start), 0, start)]
    visited = {start}

    while open_set:
        f, g, state = heapq.heappop(open_set)
        if state == goal:
            return g
        zero = state.index(0)
        for npos in neighbors[zero]:
            lst = list(state)
            lst[zero], lst[npos] = lst[npos], lst[zero]
            new_state = tuple(lst)
            if new_state not in visited:
                visited.add(new_state)
                heapq.heappush(open_set, (g + 1 + h(new_state), g + 1, new_state))
    return -1

def astar_buggy(graph, start, end, h):
    open_set = [(h(start, end), 0, start)]
    visited = set()
    while open_set:
        f, g, node = heapq.heappop(open_set)
        if node == end:
            return g
        if node in visited:
            continue
        visited.add(node)
        for neighbor, cost in graph[node]:
            heapq.heappush(open_set, (g + cost + h(neighbor, end), g + cost, neighbor))
    return -1

def bidirectional_buggy(graph, start, end):
    front, back = {start}, {end}
    steps = 0
    while front and back:
        next_front = set()
        for node in front:
            for neighbor in graph[node]:
                if neighbor in back:
                    return steps + 1
                next_front.add(neighbor)
        front = next_front
        steps += 1
    return -1