| | |
| | | |
| | | def getWaveScopeByCode_iterative(x, y, codeMatrix, cdaMatrix, radiusLen): |
| | | """ |
| | | 使用广度优先搜索(BFS)来代替递归,以避免递归深度过大的问题。 |
| | | 使用广度优先搜索(BFS)并跟踪扩展方向,以避免递归深度过大和不必要的资源浪费。 |
| | | 当遇到 'NONE' 节点时,仅在当前方向上继续扩展。 |
| | | """ |
| | | includeList = [] |
| | | existNodes = set() |
| | | queue = deque() |
| | | |
| | | originNode = {"x": x, "y": y} |
| | | currNode = {"x": x, "y": y} |
| | | queue.append(currNode) |
| | | # 初始节点,没有方向 |
| | | originNode = {"x": x, "y": y, "dir": None} |
| | | queue.append(originNode) |
| | | existNodes.add((x, y)) |
| | | |
| | | while queue: |
| | | node = queue.popleft() |
| | | node_x, node_y = node['x'], node['y'] |
| | | neighbors = [ |
| | | (node_x + 1, node_y), |
| | | (node_x - 1, node_y), |
| | | (node_x, node_y + 1), |
| | | (node_x, node_y - 1) |
| | | ] |
| | | node_x, node_y, current_dir = node['x'], node['y'], node['dir'] |
| | | |
| | | for neighbor in neighbors: |
| | | nx, ny = neighbor |
| | | # 根据当前方向决定扩展的方向 |
| | | if current_dir is None: |
| | | # 如果没有方向,向四个方向扩展 |
| | | neighbors = [ |
| | | (node_x + 1, node_y, 'right'), |
| | | (node_x - 1, node_y, 'left'), |
| | | (node_x, node_y + 1, 'down'), |
| | | (node_x, node_y - 1, 'up') |
| | | ] |
| | | else: |
| | | # 如果有方向,仅在该方向上扩展 |
| | | if current_dir == 'right': |
| | | neighbors = [(node_x + 1, node_y, 'right')] |
| | | elif current_dir == 'left': |
| | | neighbors = [(node_x - 1, node_y, 'left')] |
| | | elif current_dir == 'down': |
| | | neighbors = [(node_x, node_y + 1, 'down')] |
| | | elif current_dir == 'up': |
| | | neighbors = [(node_x, node_y - 1, 'up')] |
| | | else: |
| | | neighbors = [] |
| | | |
| | | for nx, ny, direction in neighbors: |
| | | # 检查边界条件 |
| | | if (nx < 0 or nx >= codeMatrix.shape[0] or ny < 0 or ny >= codeMatrix.shape[1]): |
| | | continue |
| | |
| | | neighbor_code = codeMatrix[nx, ny] |
| | | |
| | | if neighbor_code == 'NONE': |
| | | queue.append({"x": nx, "y": ny}) |
| | | # 遇到 'NONE' 节点,继续在当前方向上扩展 |
| | | queue.append({"x": nx, "y": ny, "dir": direction}) |
| | | else: |
| | | # 检查距离条件 |
| | | o1Cda = convert_to_float_array(cdaMatrix[x, y]) |
| | | o2Cda = convert_to_float_array(cdaMatrix[nx, ny]) |
| | | |
| | |
| | | "y": int(ny), |
| | | "code": str(codeMatrix[nx, ny]) |
| | | }) |
| | | queue.append({"x": nx, "y": ny}) |
| | | # 非 'NONE' 节点,重置方向 |
| | | queue.append({"x": nx, "y": ny, "dir": None}) |
| | | |
| | | return includeList |
| | | |