构建电路通过起始框在矩阵中水平和垂直搜索其他非空框

Question

from random import shuffle


matrix_aux_with_num_decompositions = [
    [None,  'b', None,  100,  100,   -3],
    [None, None,  200,  'a', None,  100],
    [ 100,  200, None, None, None, None],
]

matrix_aux_with_num_decompositions_aux = [
    [     -1, 'asign',      -3, 'asign', 'asign',      -3],
    [      5,       4, 'asign', 'asign',      -2, 'asign'],
    ['asign', 'asign',      -9,      -3,      -1,      -5],
]

#Possible coordinates of lockers that will function as starting points for the possible circuit
#Note that they are the coordinates of the only positive values within the matrix called matrix_aux_with_num_decompositions_aux
coords_posibles_elementos_de_partida = [ [1, 0], [1, 1] ]
#optionally we can exchange the starting points to analyze them randomly
shuffle(coords_posibles_elementos_de_partida)

我需要尝试列表 coords_posibles_elementos_de_partida 中每一个坐标（格式为 [行, 列]），直到找到一个可以构建闭合电路的坐标。这个电路必须遵循只能水平和垂直提取数据的规则，并且必须在起点结束，也就是说，最后要回到从 coords_posibles_elementos_de_partida 中选择的坐标。

其余的坐标我们称之为顶点，这些顶点的值必须不同于 None，并且要在矩阵 matrix_aux_with_num_decompositions 的范围内。

电路 不能有对角线连接，并且必须是闭合的。例如，如果电路从 [1, 0] 开始，它必须在 matrix_aux_with_num_decompositions 中循环经过不同于 None 的值，并将这些值作为顶点。

输出列表的表达方式应该是：

[[起点行, 起点列], [第一个顶点行, 第一个顶点列], ..., [第i个顶点行, 第i个顶点列]]

这个列表会是一个可能的正确列表（正确的输出），其中顶点按顺序列出，从起点开始（并且要闭合，因为它要回到起点）。

circuit_list = [[1, 0], [1, 3], [0, 3], [0, 1], [2, 1], [2,0] ]

在最后一个顶点之后，比如 [2, 0]，电路会返回到起点 [1, 0]，因为电路是闭合的。

这是我的代码，但它的逻辑并没有正确工作。

def is_valid_move(matrix, visited, row, col):
    # Check if the move is within the matrix boundaries and the cell is not visited
    return 0 <= row < len(matrix) and 0 <= col < len(matrix[0]) and not visited[row][col] and matrix[row][col] is not None

#Depth-First Search is a graph traversal algorithm used to explore nodes and edges of a graph
def dfs(matrix, visited, row, col, start_row, start_col, path):
    # Define the possible moves: up, down, left, right
    moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Mark the current cell as visited
    visited[row][col] = True

    # Append the current cell to the path
    path.append([row, col])

    # If the current cell is the starting cell and all cells are visited, return the path
    if row == start_row and col == start_col and all(all(cell for cell in row) for row in visited):
        return path

    # Explore all possible moves
    for move in moves:
        new_row, new_col = row + move[0], col + move[1]
        if is_valid_move(matrix, visited, new_row, new_col):
            result = dfs(matrix, visited, new_row, new_col, start_row, start_col, path)
            if result:
                return result

    # If no valid moves left, backtrack
    visited[row][col] = False
    path.pop()
    return None

def find_circuit(matrix, start_coords):
    for start_coord in start_coords:
        start_row, start_col = start_coord
        visited = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        path = []

        circuit = dfs(matrix, visited, start_row, start_col, start_row, start_col, path)

        if circuit:
            return circuit

    return None

# Find a possible closed loop
circuit = find_circuit(matrix_aux_with_num_decompositions, coords_posibles_elementos_de_partida)

# Print Circuit Vertex List
if circuit:
    print("Circuit found: ")
    print(circuit)
else:
    print("No closed circuit found.")

但是不幸的是，我的代码出错了，它错误地表示没有可能的电路，但这并不正确，因为在下面的图片中，我们可以看到至少可以画出一个电路。

这里是图片

这里有一张关于可能和不可能电路的示例图片：

可能和不可能的电路

数据结构坐标系统顶点算法逻辑闭合电路矩阵搜索水平垂直提取图形表示

构建电路通过起始框在矩阵中水平和垂直搜索其他非空框

1 个回答

撰写回答