Прикреплённый файл «2014-04-18-knight5.py»
Загрузка 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 Jump=(2,-1),(2,1),(1,2),(-1,2)
19
20 def front():
21
22 def dump(full=False):
23 print "Maximal front:",mlen
24 if not full: return
25 SS={}
26 for S in Sum:
27 SS.update(S)
28 for y in xrange(N):
29 print "".join(["{:<5}".format(SS.get((x,y),".")) for x in xrange(M)])
30 print
31
32 mlen=1
33 Sum=[{},{},{(0,0):1}]
34 for i in xrange(1,M+N-1):
35 Sum.append({})
36 for m in xrange(i+1):
37 n=i-m
38 Sum[-1][(m,n)]=sum(Sum[-dm-dn-1].get((m-dm,n-dn),0) for dm,dn in Jump if 0<=m-dm<M and 0<=n-dn<N)
39 Sum.pop(0)
40 mlen=max(mlen,sum(map(len, Sum)))
41 dump(M*N<100)
42 return Sum[-1][(M-1,N-1)]
43
44 def req(m,n):
45 if not 0<=m<M or not 0<=n<N:
46 return 0
47 elif m == n == 0:
48 return 1
49 return sum(req(m-dm,n-dn) for dm,dn in Jump)
50
51 M,N = len(sys.argv)>2 and (int(sys.argv[1]),int(sys.argv[2])) or (7,10)
52 if (M+N)%3!=2:
53 print "No way"
54 sys.exit(0)
55
56 print front()
57 print req(M-1,N-1)
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2014-04-25 13:18:59, 1.4 KB) [[attachment:2014-04-18-knight.py]]
- [получить | показать] (2014-04-25 13:19:11, 1.9 KB) [[attachment:2014-04-18-knight2.py]]
- [получить | показать] (2014-04-25 13:19:23, 1.8 KB) [[attachment:2014-04-18-knight5.py]]
- [получить | показать] (2014-04-25 13:18:47, 1.0 KB) [[attachment:2014-04-18-payedladder.py]]
Вам нельзя прикреплять файлы к этой странице.