Статья Автор: Щурова Ольга

ЕГЭ-18 задание

# Задача 4 из зачёта
# Первый способ(динамика)

def mas_min(matrix):
    m,n=len(matrix), len(matrix[0])
    matrix_mn=[[10**20]*m for i in range(n)]
    matrix_mn[0][0]=matrix[0][0]
    for i in range(1,m):
        if matrix[0][i] > 0: matrix_mn[0][i]=matrix_mn[0][i-1]+matrix[0][i]    # проходимся по первой строчке
    for i in range(1,n):
        if matrix[i][0] > 0: matrix_mn[i][0]=matrix_mn[i-1][0]+matrix[i][0]    # проходимся по первому столбцу    
        
    for r in range(1,n):        # проходимся по оставшимся клеткам
      for c in range(1,m):
          k=matrix[r][c]
          if k!=-1: 
            k1=matrix_mn[r-1][c]
            k2=matrix_mn[r][c-1]
            matrix_mn[r][c]=min(k1,k2)+k
    return matrix_mn
        

def mas_max(matrix):
    m,n=len(matrix), len(matrix[0])
    matrix_mx=[[-1*(10**20)]*m for i in range(n)]
    matrix_mx[0][0]=matrix[0][0]
    for i in range(1,m):
        if matrix[0][i] > 0: matrix_mx[0][i]=matrix_mx[0][i-1]+matrix[0][i]
    for i in range(1,n):
        if matrix[i][0] > 0: matrix_mx[i][0]=matrix_mx[i-1][0]+matrix[i][0]          
    for r in range(1,n):
      for c in range(1,m):
          k=matrix[r][c]
          if k!=-1:
            k1=matrix_mx[r-1][c]
            k2=matrix_mx[r][c-1]
            matrix_mx[r][c]=max(k1,k2)+k
    return matrix_mx

def input_matrix(name):  # ввод
    matrix=[]
    with open(name,'r') as file:
        for line in file:
            A=list(map(int,line.split()))
            matrix.append(A)
    return matrix


name=input()
mas=input_matrix(name)
min_mas= mas_min(mas)
n=len(min_mas)
m=len(min_mas[0])
output=[]
for r in range(n):  # вывод значений в финальных точках
    for c in range(m):
        if mas[r][c]!= -1 and (r+1==n or mas[r+1][c]==-1) and (c+1==m or mas[r][c+1]==-1):
            output.append(min_mas[r][c])
print(len(output))
print(min(output))
output=[]
max_mas= mas_max(mas)
for r in range(n): # проходимся по первой строчке
    for c in range(m):
        if mas[r][c]!= -1 and (r+1==n or mas[r+1][c]==-1) and (c+1==m or mas[r][c+1]==-1):
            output.append(max_mas[r][c])
print(max(output))

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать