路径查找算法练习和使用 .txt 文件

Question

这是给我的作业，我一直在努力写解决方案。

编写一个程序，找出矩阵（二维网格）中最长的相邻颜色序列。颜色由“R”、“G”、“B”字符（分别为红色、绿色和蓝色）表示。
您将获得 4 个单独的测试用例，它们也必须包含在您的解决方案中。
您的解决方案根目录示例应如下所示：

solutionRootDir
| - (my solution files and folders)
| - tests/
| - test_1
| - test_2
| - test_3
| - test_4

单个测试用例输入格式：

首先，您应该从提供的测试用例中读取两个以空格分隔的 32 位整数
表示矩阵的大小（行和列）。
接下来您应该阅读换行符分隔的 8 位字符行的行数。你的程序应该找到并打印最长的相邻序列（对角线不计为相邻字段），并将数字打印到标准输出。注意：如果有多个序列具有相同的长度——只需打印它们相同的长度即可。

test_1
Provided input:
3 3
R R B
G G R
R B G
Expected Output:
2

test_2
Provided input:
4 4
R R R G
G B R G
R G G G
G G B B
Expected Output:
7

test_3
Provided input:
6 6
R R B B B B
B R B B G B
B G G B R B
B B R B G B
R B R B R B
R B B B G B
Expected Output: 22

test_4
Provided input:
1000 1000
1000 rows of 1000 R’s
Expected Output:
1000000

您的程序入口点应接受一到四个附加参数。这些参数将指示您的程序应该运行.

• 示例 1：./myprogram test_1 test_3

• 示例 2：./myprogram test_1 test_2 test_3 test_4

• 您可以假设用户的输入是正确的（不需要验证）

import numpy as np

a = int(input("Enter rows: "))
b = int(input("Enter columns: "))
rgb = ["R", "G", "B"]
T = [[0 for col in range(b)] for row in range(a)]

for row in range(a):
    for col in range(b):
        T[row][col] = np.random.choice(rgb)

for r in T:
    for c in r:
        print(c, end=" ")
    print()

def solution(t):
    rows: int = len(t)
    cols: int = len(t[0])
    longest = np.empty((rows, cols))
    longest_sean = 1

    for i in range(rows - 1, -1, -1):
        for j in range(cols - 1, -1, -1):
            target = t[i][j]

            current = 1

            for ii in range(i, rows):
                for jj in range(j, cols):
                    length = 1
                    if target == t[ii][jj]:
                        length += longest[ii][jj]
                    current = max(current, length)

            longest[i][j] = current
            longest_sean = max(current, longest_sean)

    return longest_sean

print(solution(T))

Answer 1

为了从控制台执行中获取参数，您必须使用 sys.argv 所以 from sys import argv。而不是将您的文本字段转换为 python 这样的列表

def load(file):
    with open(file+".txt") as f:
        data = f.readlines()
    res = []
    for row in data:
        res.append([])
        for element in row:
            if element != "\n" and element != " ":
                res[-1].append(element)

    return res

将创建一个包含 "R"、"B" 和 "G" 的二维列表。而不是您可以像使用此函数一样简单地查找一个值的最长区域：

def findLargest(data):
    visited = []
    area = []
    length = 0
    movement = [(1,0), (0,1), (-1,0),(0,-1)]

    def recScan(x, y, scanArea):
        visited.append((x,y))
        scanArea.append((x,y))
        
        for dx, dy in movement:
            newX, newY = x+dx, y+dy
            if newX >= 0 and newY >= 0 and newX < len(data) and newY < len(data[newX]):
                if data[x][y] == data[newX][newY] and (not (newX, newY) in visited):
                    recScan(newX, newY, scanArea)
        return scanArea
            

    for x in range(len(data)):
        for y in range(len(data[x])):
            if (x, y) not in visited:
                newArea = recScan(x, y, [])
                if len(newArea) > length:
                    length = len(newArea)
                    area = newArea
    return length, area

由此 recScan 将检查所有未访问 jet 的相邻字段。而不是像这样调用函数：

if __name__ == "__main__":
    for file in argv[1:]:
        data = load(file)
        print(findLargest(data))

argv[1:] 是必需的，因为传递给 python 的第一个参数是您要执行的文件。我的数据结构是。

main.py
test_1.txt
test_2.txt
test_3.txt
test_4.txt

和 test_1 抛出 test_4 看起来像这样只是其他值。

R R B B B B
B R B B G B
B G G B R B
B B R B G B
R B R B R B
R B B B G B

路径查找算法练习和使用 .txt 文件

Path finding algorithm excercise and working with .txt files

python

path-finding