прикреплённый файл:2014-04-18-knight2.py к странице LecturesVMSH/Python/2014-04-18

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:
   5     -- -- -- --
   6    |  |  |  |1 |
   7     -- -- -- --
   8    |  |K |  |  |
   9     -- -- -- --
  10    |  |  |  |2 |
  11     -- -- -- --
  12    |4 |  |3 |  |
  13     -- -- -- --
  14 Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
  15 '''
  16 import sys
  17 
  18 M,N = len(sys.argv)>2 and (int(sys.argv[1]),int(sys.argv[2])) or (7,10)
  19 if (M+N)%3!=2:
  20     print "No way"
  21     sys.exit(0)
  22 
  23 Jump=(2,-1),(2,1),(1,2),(-1,2)
  24 
  25 def front():
  26 
  27     def dump(full=False):
  28         '''Отладочная фцнкция'''
  29         print "Maximal front:",mlen
  30         if not full: return
  31         SS={}
  32         for S in Sum:
  33             SS.update(S)
  34         for y in xrange(1,N+1):
  35             print "".join(["{:<5}".format(SS.get((x,y),".")) for x in xrange(1,M+1)])
  36             print
  37 
  38     Sum=[{(1,1):1},{},{},{}]
  39     mlen=1          # ширина фронта, нужна только для оценки
  40     for i in xrange(1,M+N-1):
  41         for (m,n),v in Sum.pop(0).items():
  42             for dm,dn in Jump:
  43                mm, nn, k = m+dm, n+dn, dm+dn-1
  44                if 0<nn<=N and 0<mm<=M:
  45                     Sum[k][(mm,nn)]=Sum[k].get((mm,nn),0)+v
  46         mlen=max(mlen,sum(map(len, Sum)))
  47         Sum.append({})
  48         dump(M*N<100)
  49     return Sum[0][(M,N)]
  50 
  51 def req(m=M,n=N):
  52     if not 0<n<=N or not 0<m<=M:
  53         return 0
  54     if m == n == 1:
  55         return 1
  56     return sum(req(m-dm, n-dn) for dm,dn in Jump)
  57 
  58 print front()
  59 print req()