Python-сообщество

Petr1992 · Окт. 14, 2020 20:17:19

Добрый день!

Уже второй день бьюсь над следующей задачей:

Дан файл “.txt”. Первая строка содержит целое нечётное число m в диапазоне от 1 до 1000 — количество строк и столбцов матрицы. В каждой из следующих m строк даны m целых чисел в диапазоне от -1000 до 1000, разделённых пробелом.
Необходимо прочитать значения матрицы по спирали, начиная от центра вверх и далее по часовой стрелке.

Язык - Python 3.7.3
Ограничение времени - 1.5 секунд
Ограничение памяти - 38Mb

Пример:
Ввод
3
9 10 7
0 7 7
8 3 4
Вывод
7
10
7
7
4
3
8
0
9

Из всех придуманных решений, прикладываю два наиболее удачных, однако оба решения не проходят либо по памяти, либо по времени

Решение 1 (не проходим по памяти)

 rows = []
started = True
with open('input.txt', 'r') as file:
    for row in file:
        if started is True:
            n = int(row.strip())
            started = False
        else:
            rows.append(row.strip().split(' '))
result = []
circle = 0
center_point = int((n-1)/2)
for _ in range(center_point):
    left, right, upper, lower = [], [], [], []
    n_1_circle = n-1-circle
    
    for i in range(circle, n-circle):
        left.append(rows[i][circle])
        right.append(rows[i][n_1_circle])
        if i == circle:
            upper = rows[i][circle+1:n_1_circle]
        if i == n_1_circle:
            lower = rows[i][circle+1:n_1_circle]
    right.reverse()
    upper.reverse()
    
    result += left
    result += lower
    result += right
    result += upper
    circle += 1
result.append(rows[center_point][center_point])
result.reverse()
with open('output.txt', 'w') as file:
    file.write('\n'.join(result))

Решение 2 (не проходим по скорости)

 with open('input.txt', 'r') as file:
    rows = file.readlines()
    
n = int(rows[0])
rows = [row.strip() for row in rows[1:]]
result = []
circle = 0
center_point = int((n-1)/2)
for _ in range(center_point):
    left, right, upper, lower = [], [], [], []
    n_1_circle = n-1-circle
    
    for i in range(circle, n-circle):
        temp = rows[i].split(' ')
        left.append(temp[circle])
        right.append(temp[n_1_circle])
        if i == circle:
            upper = temp[circle+1:n_1_circle]
        if i == n_1_circle:
            lower = temp[circle+1:n_1_circle]
    right.reverse()
    upper.reverse()
    
    result += left
    result += lower
    result += right
    result += upper
    circle += 1
result.append(rows[center_point].split(' ')[center_point])
result.reverse()
with open('output.txt', 'w') as file:
    file.write('\n'.join(result))

Очень прошу помочь найти правильное решение задачи.

py.user.next · Окт. 15, 2020 03:27:42

Сделал через конечный автомат.

[guest@localhost mtx_spiral]$ ls
input.txt  mtx_spiral.py  test_mtx_spiral.py
[guest@localhost mtx_spiral]$ ./mtx_spiral.py 
[guest@localhost mtx_spiral]$ ls
input.txt  mtx_spiral.py  output.txt  test_mtx_spiral.py
[guest@localhost mtx_spiral]$ cat input.txt 
3
9 10 7
0 7 7
8 3 4
[guest@localhost mtx_spiral]$ cat output.txt 
7
10
7
7
4
3
8
0
9
[guest@localhost mtx_spiral]$

Прикреплённый файлы:
mtx_spiral.tar.gz (2,1 KБ)

Python-сообщество

Уведомления

#1 Окт. 14, 2020 20:17:19

Задача на чтение матрицы по спирали с ограничениями на время и память

#2 Окт. 15, 2020 03:27:42

Задача на чтение матрицы по спирали с ограничениями на время и память

Board footer