Есть ли способ ускорить его работу и уменьшить избыточность? [закрыто] ⇐ Python

[Anonymous]

вот мой код для решения Волшебной шахматной доски на Кэттисе:

Код: Выделить всё

import sys

def read():

input_data = sys.stdin.read().strip().split()

rows = int(input_data[0])
cols = int(input_data[1])
grid = []
index = 2  # Start after the dimensions

for i in range(rows):
row = [int(input_data[index + j]) for j in range(cols)]
grid.append(row)
index += cols

return rows, cols, grid

def fill_diagonal(matrix, row, col, rows, cols):

changed = False
if matrix[row][col] != 0:
if isinstance(matrix[row][col], int):
parity = matrix[row][col] % 2
else:
parity = -1

if parity == 0 or matrix[row][col] == "P":
if row > 0 and col > 0 and matrix[row - 1][col - 1] == 0:
matrix[row - 1][col - 1] = "I"
changed = True
if row > 0 and col < cols - 1 and matrix[row - 1][col + 1] == 0:
matrix[row - 1][col + 1] = "I"
changed = True
if row < rows - 1 and col > 0 and matrix[row + 1][col - 1] == 0:
matrix[row + 1][col - 1] = "I"
changed = True
if row < rows - 1 and col < cols - 1 and matrix[row + 1][col + 1] == 0:
matrix[row + 1][col + 1] = "I"
changed = True

if parity == 1 or matrix[row][col] == "I":
if row > 0 and col > 0 and matrix[row - 1][col - 1] == 0:
matrix[row - 1][col - 1] = "P"
changed = True
if row > 0 and col < cols - 1 and matrix[row - 1][col + 1] == 0:
matrix[row - 1][col + 1] = "P"
changed = True
if row < rows - 1 and col > 0 and matrix[row + 1][col - 1] == 0:
matrix[row + 1][col - 1] = "P"
changed = True
if row < rows - 1 and col < cols - 1 and matrix[row + 1][col + 1] == 0:
matrix[row + 1][col + 1] = "P"
changed = True

return changed

def fill_remaining_zeros(matrix,row,col,rows,cols):

changed = False
if rows > cols:
if matrix[row][col] != 0:
if isinstance(matrix[row][col], int):
parity = matrix[row][col] % 2
else:
parity = -1
if parity == 0 or matrix[row][col] == "P":
if row > 0 and matrix[row - 1][col] == 0:
matrix[row - 1][col] = "I"
changed = True
elif row < rows - 1 and matrix[row + 1][col] == 0:
matrix[row + 1][col] = "I"
changed = True

if parity == 1 or matrix[row][col] == "I":
if row > 0 and matrix[row - 1][col] == 0:
matrix[row - 1][col] = "P"
changed = True
elif row < rows - 1 and matrix[row + 1][col] == 0:
matrix[row + 1][col] = "P"
changed = True

else:
if matrix[row][col] != 0:
if isinstance(matrix[row][col], int):
parity = matrix[row][col] % 2
else:
parity = -1
if parity == 0 or matrix[row][col] == "P":
if col > 0 and matrix[row][col-1] == 0:
matrix[row][col-1] = "I"
changed = True
elif col < cols - 1 and matrix[row][col+1] == 0:
matrix[row][col+1] = "I"
changed = True

elif parity == 1 or matrix[row][col] == "I":
if col > 0 and matrix[row][col-1] == 0:
matrix[row][col-1] = "P"
changed = True
elif col < cols - 1 and matrix[row][col+1] == 0:
matrix[row][col+1] = "P"
changed = True

return changed

def fill_all_zeros(matrix, rows, cols):

if rows >  cols:
# si on a plus de lignes que des colonnes, on alterne par ligne
for col in range(cols):
for row in range(rows):
if matrix [row][col] == 0:
if row % 2 == 0:
matrix[row][col] = "I"
else:
matrix[row][col] = "P"
else:
# si on a plus de colonnes que des lignes, on alterne par colonne
for row in range(rows):
for col in range(cols):
if matrix [row][col] == 0:
if col % 2 == 0:
matrix[row][col] = "I"
else:
matrix[row][col] = "P"

def fill_matrix(matrix, rows, cols):

while True:
changed = False
for row in range(rows):
for col in range(cols):
if fill_diagonal(matrix, row, col, rows, cols) :
changed = True
if not changed:
break

while True:
changed = False
for row in range(rows):
for col in range(cols):
if fill_remaining_zeros(matrix, row, col, rows, cols):
changed = True
if not changed:
break

fill_all_zeros(matrix,rows,cols)

return matrix

def fill_grid(matrix, rows, cols):

total_sum = 0
if rows > cols:
for col in range(cols):
for row in range(rows):
if matrix[row][col] == "P" or matrix[row][col] == 0:
max_neighbor = 0
if col > 0:
max_neighbor = max(max_neighbor, matrix[row][col - 1])
if row > 0:
max_neighbor = max(max_neighbor, matrix[row - 1][col])
num = max_neighbor + 1
if matrix[row][col] == "P" and num % 2 != 0:
num += 1
matrix[row][col] = num
total_sum += num
elif matrix[row][col] == "I" or matrix[row][col] == 0:
max_neighbor = 0
if col > 0:
max_neighbor = max(max_neighbor, matrix[row][col - 1])
if row > 0:
max_neighbor = max(max_neighbor, matrix[row - 1][col])
num = max_neighbor + 1
if matrix[row][col] == "I" and num % 2 != 1:
num += 1
matrix[row][col] = num
total_sum += num
else:
total_sum += matrix[row][col]
else:
for row in range(rows):
for col in range(cols):
if matrix[row][col] == "P" or matrix[row][col] == 0:
max_neighbor = 0
if col > 0:
max_neighbor = max(max_neighbor, matrix[row][col - 1])
if row > 0:
max_neighbor = max(max_neighbor, matrix[row - 1][col])
num = max_neighbor + 1
if matrix[row][col] == "P" and num % 2 != 0:
num += 1
matrix[row][col] = num
total_sum += num
elif matrix[row][col] == "I" or matrix[row][col] == 0:
max_neighbor = 0
if col > 0:
max_neighbor = max(max_neighbor, matrix[row][col - 1])
if row > 0:
max_neighbor = max(max_neighbor, matrix[row - 1][col])
num = max_neighbor + 1
if matrix[row][col] == "I"  and num % 2 != 1:
num += 1
matrix[row][col] = num
total_sum += num
else:
total_sum += matrix[row][col]

return matrix, total_sum

def is_valid_lot_numbering(grid):
rows = len(grid)
cols = len(grid[0])

for row in grid:
for i in range(len(row) - 1):
if row[i] >= row[i + 1]:
return False

for col in range(cols):
for row in range(rows - 1):
if grid[row][col] >= grid[row + 1][col]:
return False

for row in range(rows):
for col in range(cols):
current_lot = grid[row][col]
if row > 0 and col > 0 and (current_lot % 2 == grid[row - 1][col - 1] % 2):
return False
if row > 0 and col < cols - 1 and (current_lot % 2 == grid[row - 1][col + 1] % 2):
return False
if row < rows - 1 and col > 0 and (current_lot % 2 == grid[row + 1][col - 1] % 2):
return False
if row < rows - 1 and col < cols - 1 and (current_lot % 2 == grid[row + 1][col + 1] % 2):
return False

return True

def main():

rows, cols, matrix = read()
fill_matrix(matrix, rows, cols)
full_mat = fill_grid(matrix, rows, cols)
result, total_sum = full_mat
if not is_valid_lot_numbering(matrix):
print("-1")
else:
print(total_sum)

if __name__ == "__main__":
main()

Я новичок в программировании, поэтому не знаю, как оптимизировать этот код, чтобы он работал быстрее, логика работает, единственная проблема в том, что обработка больших файлов занимает очень много времени. записи. Я знаю, что здесь много избыточности, но не знаю, как я могу это исправить, не имея проблем после этого.
Я пробовал использовать deque, но, поскольку не знаю, как его правильно использовать, я получаю неправильные ответы. Я также думал об использовании рекурсии для заполнения матрицы вместо цикла while, но я также не знаю, как ее правильно использовать и действительно ли это быстрее.

Подробнее здесь: https://stackoverflow.com/questions/785 ... redundancy