Attachment '2013-03-22.turtle.py'

Download

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 «Маршрут черепашки» (MCCME). В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
   5 Формат входных данных. В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
   6 Формат выходных данных. Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
   7 '''
   8 
   9 import sys
  10 
  11 if len(sys.argv)>1:
  12     # Генератор
  13     import random
  14 
  15     N=sys.argv[1].isdigit() and int(sys.argv[1]) or random.randint(90,100)
  16     M=len(sys.argv)>2 and sys.argv[2].isdigit() and int(sys.argv[2]) or random.randint(N*4/5,N*6/5)
  17     print "{0} {1}".format(N,M)
  18     print "\n".join((" ".join("{0:3}".format(random.randint(0,100)) for i in xrange(M))) for j in xrange(N))
  19     sys.exit(0)
  20 
  21 N,M=(int(k) for k in raw_input().split())
  22 A=[[int(k) for k in raw_input().split()] for i in xrange(N)]
  23 R=[[0]*M for i in xrange(N)]
  24 
  25 def mxpath():
  26     # R -- массив с решениями задачи для каждой клетки
  27     R[0][0]=A[0][0]
  28     # Строка #0
  29     for i in xrange(1,M): R[0][i]=R[0][i-1]+A[0][i]
  30     # Столбец #0
  31     for j in xrange(1,N): R[j][0]=R[j-1][0]+A[j][0]
  32     for s in xrange(2,N+M-1):
  33         for i in xrange(max(1,s-M+1),min(N,s)):
  34             R[i][s-i]=max(R[i-1][s-i],R[i][s-i-1])+A[i][s-i]
  35     return R[N-1][M-1]
  36 
  37 def backagain():
  38     i,j,ret=N-1,M-1,""
  39     while i or j:
  40         if j==0 or i>0 and R[i-1][j]>R[i][j-1]:
  41             ret="D"+ret
  42             i-=1
  43         else:
  44             ret="R"+ret
  45             j-=1
  46     return ret
  47 
  48 mxpath()
  49 
  50 #import pprint
  51 #pprint.pprint(A)
  52 #pprint.pprint(R)
  53 
  54 print backagain()

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.