Python矩阵赛博朋克解算器

Question

我有如下输入数据：

4              #length of way
BD 1C BD 55    #way
5              #matrix size (5x5 now)
1C BD 1C 55 55 #matrix
55 55 55 1C 1C
E9 1C 55 55 E9
BD 1C 1C 1C BD
55 BD E9 55 1C

我需要用正确的方法来求解矩阵。解决问题的规则如下：

1. 在这个输入中，我要找到一个BD 1C BD 55代码。我取第一行（1C BD 1C 55 55）并在其中找到BD。这是第二个要素
2. 现在我取第二个垂直（BD 55 1C 1C BD）并在其中找到1C。它可以是第三和第四。这就是我现在的问题。程序应检查第三路和第四路。如您所见，在第三行（E9 1C 55 55 E9）中没有BD元素，但在第四行（BD 1C 1C 1C BD)）中有一个BD元素。因此它是第一个元素
3. 现在我继续寻找这个直到找到为止。所以我打印这个方法，这个输入的答案是2 4 1 2。如果有多个答案，我可以选择任何一个。 Here is the visualisating

这是我的密码

arrway = []
waylen = int(input())
wayin = list(map(str, input().split()))
for i in range(waylen):
    arrway.append(wayin[i])
k = int(input())
array = [[0 for j in range(k)] for i in range(k)]

for i in range(k):
    a = list(map(str, input().split()))
    for j in range(k):
        array[i][j] = a[j]
ANS = []
##############
print(array)
# The array for the example is [['1C', 'BD', '1C', '55', '55'], ['55', '55', '55', '1C', '1C'], ['E9', '1C', '55', '55', 'E9'], ['BD', '1C', '1C', '1C', 'BD'], ['55', 'BD', 'E9', '55', '1C']]
#############
currentNum = 0
currentPos = 0
for i in range(waylen):
    currentElement = arrway[currentNum]
    if i % 2 == 0:
        for jk in range(k):  # horizontal
            if array[currentPos][jk] == currentElement:
                ANS.append(jk + 1)

                currentPos = jk
                currentNum += 1
    else:
        for jkl in range(k):  # vertical
            if array[jkl][currentPos] == currentElement:
                ANS.append(jkl + 1)

                currentPos = jkl
                currentNum += 1
##########
print(ANS)
# the ANS for example is [2, 3, 4, 1, 2] but no [2, 4, 1, 2]. 
##########

如你所见，问题在于检查几个元素的正确方式。现在我的代码有了二维矩阵数组

希望你能帮助我。谢谢

Answer 1

如果您的输入相当小，那么您可以尝试使用递归（但是如果输入很大，您可能会因堆栈溢出而失败）

首先调用find_on_row，给它整个way元素列表、整个数组，以及我们找到的当前way元素的索引（开始时为0）和要搜索的行的索引（开始时为0，如您所说）

find_on_row遍历指定行中的所有元素，对于每个元素，它调用find_on_col函数所需的方式元素相等（因为第一行上只有一次BD，所以使用此列调用函数find_on_col

find_on_col做了类似的事情-它检查指定列中的所有元素，查找下一个元素，并为每个匹配调用find_on_row（在本例中为2次，因为在第一列上可以找到两次1C）

这两个调用现在分别搜索答案，一个从第三行开始，另一个从第四行开始。它们一直搜索到找到整个路径（即way_index是最大可能），或者如果当前路径元素不匹配（因此此搜索路径没有答案）

def find_on_row(way, array, way_index, row_index):
    if way_index == len(way): # found answer
        return []
    for col_index in range(len(array[0])):
        if array[row_index][col_index]== way[way_index]:
            candidate_answer = find_on_col(way, array, way_index + 1, col_index)
            if not candidate_answer is None: # unwind answer
                return [col_index] + candidate_answer
    return None

def find_on_col(way, array, way_index, col_index):
    if way_index == len(way): # found answer
        return []
    for row_index in range(len(array)):
        if array[row_index][col_index] == way[way_index]:
            candidate_answer = find_on_row(way, array, way_index + 1, row_index)
            if not candidate_answer is None: # unwind answer
                return [row_index] + candidate_answer
    return None

way = ['BD', '1C', 'BD', '55']

array = [['1C', 'BD', '1C', '55', '55'], ['55', '55', '55', '1C', '1C'], ['E9', '1C', '55', '55', 'E9'], ['BD', '1C', '1C', '1C', 'BD'], ['55', 'BD', 'E9', '55', '1C']]

print(f'Starting from first row the answer is {find_on_row(way, array, 0, 0)}')
# Starting from first row the answer is [1, 3, 0, 1]

它从0开始打印索引，因此为了获得所需的输出，可以将每个值增加1（我不这样做，因为从0开始使用索引更方便）