华为OD机试 - 勇攀数字高峰(Python)

import sysdef solve_dfs_recursive():    data = list(map(int, sys.stdin.read().split()))    if not data:        return    idx = 0    n, m, D = data[idx], data[idx+1], data[idx+2]    idx += 3    grid = []    for i in range(n):        row = data[idx:idx+m]        idx += m        grid.append(row)    # 找到最低点和最高点    min_val = min(min(row) for row in grid)    max_val = max(max(row) for row in grid)    start = end = None    for i in range(n):        for j in range(m):            if grid[i][j] == min_val:                start = (i, j)            if grid[i][j] == max_val:                end = (i, j)    visited = [[False] * m for _ in range(n)]    directions = [(0,1),(1,0),(0,-1),(-1,0)]    count = 0    def dfs(x, y):        nonlocal count        if (x, y) == end:            count += 1            return        for dx, dy in directions:            nx, ny = x + dx, y + dy            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:                diff = grid[nx][ny] - grid[x][y]                if diff > 0 and diff <= D:                    visited[nx][ny] = True                    dfs(nx, ny)                    visited[nx][ny] = False    visited[start[0]][start[1]] = True    dfs(start[0], start[1])    print(count)if __name__ == "__main__":    solve_dfs_recursive()

import sysdef solve_dfs_iterative():    data = list(map(int, sys.stdin.read().split()))    if not data:        return    idx = 0    n, m, D = data[idx], data[idx+1], data[idx+2]    idx += 3    grid = []    for i in range(n):        row = data[idx:idx+m]        idx += m        grid.append(row)    # 找到起点和终点    min_val = min(min(row) for row in grid)    max_val = max(max(row) for row in grid)    start = end = None    for i in range(n):        for j in range(m):            if grid[i][j] == min_val:                start = (i, j)            if grid[i][j] == max_val:                end = (i, j)    directions = [(0,1),(1,0),(0,-1),(-1,0)]    # 栈元素: (x, y, visited_mask, 方向索引)    # 由于n*m<=100，可以用整数位掩码表示visited，但为简单，使用二维布尔数组的元组（不可哈希）    # 改用保存路径列表，回溯时恢复visited    # 另一种方式：栈中保存 (x, y, visited_state, next_dir_index)    # 用list of list记录visited状态，深拷贝开销大，此处用回溯思想模拟递归    # 手动模拟调用栈：    visited = [[False]*m for _ in range(n)]    visited[start[0]][start[1]] = True    # 栈元素: (x, y, 方向索引)    stack = [(start[0], start[1], 0)]    count = 0    # 记录每个位置的邻居迭代状态    # 使用显式栈模拟递归，需要保存当前节点和尝试的下一个方向索引    # 更简单：使用递归但这里要求迭代，给出另一种实现：    # 用栈存储 (x, y, visited_copy) 会超内存，改用path列表和回溯    # 采用手动模拟的方式：    # 我们用一个列表记录当前路径，每次尝试方向，类似DFS迭代器    # 重新设计：使用栈存储 (x, y, step) 并配合手动回溯，但较为复杂。    # 下面提供一种清晰但可能稍慢的实现：使用栈存储状态，每次压入新状态前复制visited（由于格子最多100，复制100*100布尔数组成本可接受）    # 但复制开销较大，不过n,m<=10，路径数量有限，可行。    # 更优雅：使用栈存储 (x, y, visited_tuple) 将visited转为元组，但元组不可变，每次创建新元组。    # 这里采用复制visited列表的方式。    # 再次实现：    visited = [[False]*m for _ in range(n)]    visited[start[0]][start[1]] = True    # 栈元素: (x, y, visited_state)    stack = [(start[0], start[1], [row[:] for row in visited])]    count = 0    while stack:        x, y, vis = stack.pop()        if (x, y) == end:            count += 1            continue        for dx, dy in directions:            nx, ny = x+dx, y+dy            if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny]:                diff = grid[nx][ny] - grid[x][y]                if 0 < diff <= D:                    new_vis = [row[:] for row in vis]                    new_vis[nx][ny] = True                    stack.append((nx, ny, new_vis))    print(count)if __name__ == "__main__":    solve_dfs_iterative()