fork download 
  1. import copy
  2.  
  3. yoko=5
  4. tate=10
  5. kuro=19
  6.  
  7. #joutai0:黒マスを横nマス(n<yoko)に入れる方法をリストアップ
  8.  
  9. joutai0 = [[] for i in range(yoko+1)]
  10. joutai0[1].extend([[0],[1]])
  11. temp=[]
  12. for i in range(2,yoko+1):
  13.     for j in range(len(joutai0[i-1])):
  14.         temp=copy.deepcopy(joutai0[i-1][j])
  15.         temp.append(0)
  16.         joutai0[i].append(copy.deepcopy(temp))
  17.         if temp[-2]==0:
  18.             temp[-1]=1
  19.             joutai0[i].append(copy.deepcopy(temp))
  20.  
  21.  
  22. #joutai1を作る。連なっている黒マスに同じ番号を振る場合の、すべてのパターン
  23.  
  24. joutai1 = []
  25.  
  26. def t(original,temp_123,checkichi,shurui):
  27.     if checkichi==yoko:
  28.         #終了。joutai1に書き込む
  29.         joutai1.append(copy.deepcopy(temp_123))
  30.     else:
  31.         if original[checkichi]==1:
  32.             for i in range(1,shurui+2):
  33.                 temp_123[checkichi]=i
  34.                 if i==shurui+1:
  35.                     shurui+=1
  36.                 t(original,temp_123,checkichi+1,shurui)
  37.         else:
  38.             t(original,temp_123,checkichi+1,shurui)
  39.  
  40. for i in range(len(joutai0[yoko])):
  41.     original=copy.deepcopy(joutai0[yoko][i])
  42.     checkichi=1
  43.     shurui=0
  44.     temp_123=[0 for i in range(yoko)]
  45.     t(original,temp_123,0,0)
  46.  
  47. #print(joutai1)
  48. print ("joutai1=",len(joutai1))
  49.  
  50.  
  51. #joutai2を作る。壁に接続している黒は1とし、他の黒マスの連なりに番号を振る
  52. joutai2=[]
  53.  
  54. for i in range(len(joutai1)):
  55.     joutaimax=max(joutai1[i])
  56.     temp=copy.deepcopy(joutai1[i])
  57.     joutai2.append(copy.deepcopy(temp))
  58.     if joutaimax==0:
  59.         continue
  60.     if joutaimax==1:
  61.         for j in range(len(joutai1[i])):
  62.             temp[j]*=2
  63.         joutai2.append(copy.deepcopy(temp))
  64.         continue
  65.     for j in range(len(joutai1[i])):
  66.         if temp[j]>0:
  67.             temp[j]+=1
  68.     joutai2.append(copy.deepcopy(temp))
  69.  
  70.     for j in range(3,joutaimax+2):
  71.         temp2=copy.deepcopy(temp)
  72.         for k in range(len(joutai1[i])):
  73.             if temp2[k]==j:
  74.                 temp2[k]=1
  75.             elif temp2[k]>j:
  76.                 temp2[k]-=1
  77.         joutai2.append(copy.deepcopy(temp2))
  78.  
  79.  
  80. #leftwallの場合、左端の黒マスが2以上になることはないので、そのような要素を削除
  81.  
  82. i=0
  83. while (i<len(joutai2)):
  84.     if joutai2[i][0]>1:
  85. #        print ("delete",joutai2[i])
  86.         joutai2.pop(i)
  87.         i-=1
  88.     i+=1
  89.  
  90. #パリティの異なるマスが同じ数(0,1を除く)になることはない
  91. i=0
  92. tyouhuku=int(yoko/2)
  93. while (i<len(joutai2)):
  94.     odd=[]
  95.     even=[]
  96.     j=0
  97.     while (j<yoko-1):
  98.         odd.append(joutai2[i][j])
  99.         j+=1
  100.         even.append(joutai2[i][j])
  101.         j+=1
  102.     if yoko%2==0:
  103.         odd.append(joutai2[i][yoko-2])
  104.         even.append(joutai2[i][yoko-1])
  105.     else:
  106.         odd.append(joutai2[i][yoko-1])
  107.     check=0
  108.     for k in range(2,tyouhuku+1):
  109.         if (k in odd)and(k in even):
  110.             check=1
  111.     if check==1:
  112.         joutai2.pop(i)
  113.         i-=1
  114.     i+=1
  115.  
  116. #print (joutai2)
  117. print ("joutai2=",len(joutai2))
  118.  
  119.  
  120. matrix_seni=[[0 for i in range(len(joutai2))] for j in range(len(joutai2))]
  121.  
  122. for i in range(len(joutai2)):
  123.     for j in range(len(joutai0[yoko])):
  124.         #黒マスが縦に並んだらスキップ
  125.         if sum([x*y for (x,y) in zip(joutai2[i],joutai0[yoko][j]) ])>0:
  126.             continue
  127.  
  128.         temp_above=copy.deepcopy(joutai2[i])
  129.         temp_below=copy.deepcopy(joutai0[yoko][j])
  130.         nogood=0
  131.         #白マス分断が生じたらnogood=1にして、スキップする
  132.  
  133.         k=0
  134. #k=0（左端）のとき
  135. #leftwallの場合、左端の黒マスが2以上になることはない
  136.         if temp_below[k]>0:
  137.             temp_below[k]=1
  138.             ur=temp_above[k+1]
  139.             if ur==1:
  140.                 nogood=1
  141.             if ur>1:
  142.                 for l in range (k+1,yoko):
  143.                     if temp_above[l]==ur:
  144.                         temp_above[l]=1
  145. #kが両端でないとき
  146.         shurui=max(temp_above)+1
  147.         #新たに現れた黒マスで、aboveに連ならないものには、aboveに無い番号を振っていく
  148.         for k in range (1,yoko-1):
  149.             if temp_below[k]>0:
  150.                 ul=temp_above[k-1]
  151.                 ur=temp_above[k+1]
  152.                 if (ul>0)and(ur>0):
  153.                     if ul==ur:
  154.                         nogood=1
  155.                     elif (ul==1)or(ur==1):
  156.                         temp_below[k]=1
  157.                         for l in range (0,yoko):
  158.                             if (temp_above[l]==ul)or(temp_above[l]==ur):
  159.                                 temp_above[l]=1
  160.                             if (temp_below[l]==ul)or(temp_below[l]==ur):
  161.                                 temp_below[l]=1
  162.                     else:
  163.                         #upperleftに統一
  164.                         temp_below[k]=ul
  165.                         for l in range (0,yoko):
  166.                             if temp_above[l]==ur:
  167.                                 temp_above[l]=ul
  168.                             if temp_below[l]==ur:
  169.                                 temp_below[l]=ul
  170.                 elif (ul==0)and(ur==0):
  171.                     shurui+=1
  172.                     temp_below[k]=shurui
  173.                 elif ul*ur==0:
  174.                     #ul,urの一方のみ0でないとき、その数を入れる
  175.                     temp_below[k]=ul+ur
  176.             if nogood==1:
  177.                 break
  178.         if nogood==1:
  179.             nogood=0
  180.             continue
  181.  
  182.         k=yoko-1
  183. #k=yoko-1(右端)のとき
  184.         if temp_below[k]>0:
  185.             if temp_above[k-1]==0:
  186.                 shurui+=1
  187.                 temp_below[k]=shurui
  188.             else:
  189.                 temp_below[k]=temp_above[k-1]
  190.  
  191.         #出力する。数字をそろえる
  192.         shurui=1
  193.         for k in range(yoko):
  194.             if temp_below[k]==2 and shurui==0:
  195.                 shurui=2
  196.             if temp_below[k]>1:
  197.                 if temp_below[k]>shurui:
  198.                     shurui+=1
  199.                     temp=temp_below[k]
  200.                     for l in range(yoko):
  201.                         if temp_below[l]==temp:
  202.                             temp_below[l]=shurui
  203.                         elif temp_below[l]==shurui:
  204.                             temp_below[l]=temp
  205.  
  206.         #matrix_seniに入力。temp_belowで検索して、該当する位置に1を入れる
  207.         jj=0
  208.         for k in range(len(joutai2)):
  209.             if joutai2[k]==temp_below:
  210.                 jj=k
  211.                 break
  212.             if k==len(joutai2)-1:
  213.                 print ("j",joutai2[i])
  214.                 print ("j",temp_above)                
  215.                 print ("j",temp_below)
  216.                 print ("")
  217.                 #この文が表示されてしまう場合、belowがjoutai2の中に存在しない
  218.         matrix_seni[i][jj]=1
  219.  
  220.  
  221. dp_shurui=len(joutai2)
  222. print ("start")
  223.  
  224. matrix_kuro=[]
  225. for k in range(dp_shurui):
  226.     count=0
  227.     for i in range(len(joutai2[k])):
  228.         if joutai2[k][i]>0:
  229.             count+=1
  230.     matrix_kuro.append(count)
  231.  
  232.  
  233. matrix_shoki=[]
  234. for k in range(dp_shurui):
  235.     if max(joutai2[k])<2:
  236.         matrix_shoki.append(1)
  237.     else:
  238.         matrix_shoki.append(0)
  239.  
  240. matrix_hyouji=[]
  241. for k in range(dp_shurui):
  242.     temp=""
  243.     for i in range(len(joutai2[k])):
  244.         if joutai2[k][i]==0:
  245.             temp+="-"
  246.         elif joutai2[k][i]==1:
  247.             temp+="X"
  248.         else:
  249.             temp+=str(joutai2[k][i])
  250.     matrix_hyouji.append(temp)
  251.  
  252. #for i in range(dp_shurui):
  253.  #   print ("")
  254. #    print ("a",joutai2[i])
  255. #
  256. #    for j in range(dp_shurui):
  257. #        if matrix_seni[i][j]==1:
  258. #            print ("b",joutai2[j])
  259.  
  260. #    print(joutai2[k])
  261. #    print (temp)
  262.  
  263. while(tate<15):
  264.     dp=[[[0 for i in range(dp_shurui+1)]for j in range(kuro+1)]for k in range(tate+1)]
  265.     #現在の行、黒マスの個数、最下列の状態の番号
  266.  
  267.     #1行目
  268.     for joutai_new in range (dp_shurui):
  269.         if matrix_shoki[joutai_new]==1:
  270.             #joutai_newが入るかチェック
  271.             kuro_new=matrix_kuro[joutai_new]
  272.             dp[1][kuro_new][joutai_new]+=1
  273.  
  274.     for tate_old in range(1,tate):
  275.         for joutai_new in range (dp_shurui):
  276.             for joutai_old in range (dp_shurui):
  277.                 if matrix_seni[joutai_old][joutai_new]==1:
  278.                 #joutai_newが入るかチェック
  279.                     for kuro_old in range (kuro+1):
  280.                         if dp[tate_old][kuro_old][joutai_old]>0:
  281.                             kuro_new=kuro_old+matrix_kuro[joutai_new]
  282. #                            print(tate_old+1,kuro_new,joutai_new)
  283.                             dp[tate_old+1][kuro_new][joutai_new]+=dp[tate_old][kuro_old][joutai_old]
  284.  
  285.     printout=0
  286.     if printout==1:
  287.         #解の一部を表示
  288.         for joutai_new in range(dp_shurui):
  289.             d=dp[tate][kuro][joutai_new]
  290.             if d>0:
  291.                 tate_comeback=tate
  292.                 kuro_comeback=kuro
  293.                 joutai_comeback=joutai_new
  294.                 print (matrix_hyouji[joutai_comeback])
  295.                 while (tate_comeback>1):
  296.                     tate_comeback-=1
  297.                     kuro_comeback-=matrix_kuro[joutai_comeback]
  298.                     for joutai_old in range(dp_shurui):
  299.                         if (matrix_seni[joutai_old][joutai_comeback]==1)and(dp[tate_comeback][kuro_comeback][joutai_old]>0):
  300.                             print (matrix_hyouji[joutai_old])
  301.                             break
  302.                     joutai_comeback=joutai_old
  303.                 print ("")
  304.  
  305.     kuroall=0
  306.     for joutai_new in range(dp_shurui):
  307.         d=dp[tate][kuro][joutai_new]
  308.         kuroall+=d
  309.     if kuroall==0:
  310.         tate-=1
  311.         kuro-=4
  312.     else:
  313.         print (kuro, kuroall)
  314.     tate+=1
  315.     kuro+=3
  316.  
Success #stdin #stdout 0.14s 7732KB
comments (?)
stdin 
Standard input is empty
stdout 
('joutai1=', 23)
('joutai2=', 35)
start
(19, 1)
(21, 2)
(22, 547)
(24, 263)
(26, 46)
https://ideone.com/FdrfdK
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!