Решение задачи ПДД с Яндекс Контест

Без пояснения   Просмотров: 1492

Совсем недавно девятиклассник Коля прибыл в Летнюю Кинематографическую Школу.

Первым делом он решил посетить киностудию. В детском лагере «Олененок», где ЛКШ проводится в этом году, проложено множество асфальтированных дорожек и их пересечения образуют перекрестки. «Олененок» — необычный лагерь, и поэтому на всех дорожках и перекрестках нарисована разметка, а так же действуют правила дорожного движения, за нарушение которых полагаются штрафы.

Киностудия расположена на юго-востоке от корпуса, в котором живет Коля, поэтому школьник решил передвигаться только на восток и на юг. Ему очень хотелось побыстрее добраться до киностудии, и потому он решил не обращать внимания на правила, и переходить перекрестки как ему вздумается. Однако, как настоящий ЛКШонок, Коля должен позаботиться о том, чтобы суммарный размер штрафов за его нарушения был минимален. Помогите ему в этом.

В вашем распоряжении карта лагеря, представляющая собой клетчатый прямоугольник N на M, в котором на пересечении i-ой строки и j-ого столбца указан размер штрафа при попадании на этот перекресток.

Корпус, в котором живет Коля находится в северо-западном углу лагеря, а киностудия — в юго-восточном. Помогите Коле добраться до места назначения, заплатив минимально возможный штраф.

Код 

n, m = map(int, input().split())
a = []
b = []

for i in range(n):
    t = list(map(int, input().split()))
    a += [t]
    b.append([0] * m)
if n == 1 and m == 1:
    print(a[0][0])
    print(1)
    print(1, 1)
    raise SystemExit
b[0][0] = a[0][0]
for i in range(1, m):
    b[0][i] = b[0][i - 1] + a[0][i]
for i in range(1, n):
    b[i][0] = b[i - 1][0] + a[i][0]
for i in range(1, n):
    for j in range(1, m):
        b[i][j] = min(b[i - 1][j], b[i][j - 1]) + a[i][j]
print(b[n - 1][m - 1])
res = [[n, m]]
n -= 1
m -= 1
while n != 0 or m != 0:
    if n == 0:
        res.append([n + 1, m])
        m -= 1
    elif m == 0:
        res.append([n, m + 1])
        n -= 1
    elif b[n - 1][m] > b[n][m - 1]:
        res.append([n + 1, m])
        m -= 1
    else:
        res.append([n, m + 1])
        n -= 1
print(len(res))
for i in range(len(res) - 1, -1, -1):
    print(*res[i])

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp