时间戳

首页 > 解决方案 > Python 矩阵赛博朋克求解器

python - Python 矩阵赛博朋克求解器

问题描述

我有这样的输入数据：

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在其中找到。可以是第3和第4。这就是我现在的问题。程序应检查第 3 路和第 4 路。如您所见，BD第三行（E9 1C 55 55 E9）中没有元素，但第四行（ ）中有一个BD元素BD 1C 1C 1C BD)。所以它是第一个元素。
  3. 现在我继续寻找这个，直到我得到所有的方式。所以我打印了方式，这个输入的答案是2 4 1 2。如果有多个答案，我可以选择任何一个。 这里是可视化

这是我的代码。

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]. 
##########

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

希望您能够帮助我。谢谢你。

标签： python

解决方案

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

您首先调用find_on_row给它整个方式元素列表，整个数组，以及我们找到的当前方式元素的索引（一开始它是 0）和你想要搜索的行的索引（一开始它是 0 ， 如你所说）。

find_on_row遍历指定行中的所有元素，并且对于每个元素等于它调用find_on_col函数所需的方式元素（因为您BD在第一行只有一次，因此该函数find_on_col在此列中调用一次。

find_on_col做类似的事情 - 它遍历指定列中的所有元素，查找下一个元素并调用find_on_row每个匹配项（在这种情况下为 2 次，因为1C可以在第一列中找到两次。

这两个调用现在分别搜索答案，一个从第 3 行开始，另一个从第 4 行开始。他们一直到找到整个方式（即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 开始的索引更方便）

推荐阅读