构建一个电路，采用起始框并尝试水平和垂直搜索矩阵中不存在的其他框

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

的每个框（以 [行，列] 形式给出），直到找到一个允许我构建闭合电路的框，遵循只能提取数据 horizontally 的规则，并且垂直，并且必须从开始的地方结束，即从

coords_posibles_elementos_de_partida

中选择的坐标数 其余的框，我们将它们称为顶点，它们必须是与

None

不同且位于矩阵

matrix_aux_with_num_decompositions

部分内的框值

电路不能有对角线连接，并且它们必须是闭合的，例如，如果它从 [1, 0] 开始，则循环遍历

matrix_aux_with_num_decompositions

内与

None

不同的值并将它们保留为顶点可能是：

#This is a possible correct vertex list(output):
circuit = [[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.")

但不幸的是，我的代码失败了，因为它错误地表明没有可能的电路，但事实并非如此，因为在下图中我们可以看到可以绘制至少一个电路。

Answer 1

通常不值得你自己这样做；使用 NetworkX 代替：

import networkx
from matplotlib import pyplot as plt

matrix = [
    [None,  'b', None,  100,  100,   -3],
    [None, None,  200,  'a', None,  100],
    [ 100,  200, None, None, None, None],
]
m = len(matrix)
n = len(matrix[0])

graph = networkx.Graph()

for i, row in enumerate(matrix):
    graph.update(
        networkx.complete_graph([
            (i, j)
            for j, elm in enumerate(row)
            if elm is not None
        ])
    )
for j in range(n):
    graph.update(
        networkx.complete_graph([
            (i, j)
            for i, row in enumerate(matrix)
            if row[j] is not None
        ])
    )

print(networkx.find_cycle(graph))

networkx.draw(graph, with_labels=True)
plt.show()

[((0, 1), (0, 3)), ((0, 3), (0, 4)), ((0, 4), (0, 1))]