fork download
copy 
  1. '''
  2. 0401 PA05
  3. 21800279 Seonyeong Park
  4. Polyomino Puzzle: To find a solution of puzzle for given polyominos
  5. '''
  6. import numpy as np
  7. import math
  8. import copy
  9.  
  10. #input
  11. n = int(input())
  12. blocks = []
  13. count = 0
  14. for i in range(n):
  15.     h,w = [int(x) for x in input().split()]
  16.     blocks.append([(h,w)])
  17.     for j in range(h):
  18.         line = [int(x) for x in input().split()]
  19.         for b in line:
  20.             if b == 1:
  21.                 count+=1
  22.         blocks[i].append(line)
  23.  
  24. def check(c):
  25.     s = math.sqrt(c)
  26.     if s == int(s):
  27.         for block in blocks:
  28.             for line in block[0]:
  29.                 if line > s:
  30.                     return False
  31.         return int(s)
  32.     return False
  33.  
  34. def puzzle(num,ans,row,col):
  35.     b = blocks[num]
  36.     h,w = b[0]
  37.     res = copy.deepcopy(ans)
  38.     for i in range(h):
  39.         for j in range(w):
  40.             if b[i+1][j] == 1:
  41.                 if ans[row+i][col+j] == 0:
  42.                     res[row+i][col+j] = num+1
  43.                 else:
  44.                     return False
  45.     for i in range(side):
  46.         for j in range(side):
  47.             if res[i][j] == 0:
  48.                 return [res, i, j]
  49.     return [res, i, j]
  50.  
  51. def polyomino(pro,ans,num=0,row=0,col=0,put=[],turn=0):
  52.     print(ans)
  53.     if len(put) == n:
  54.         return ans
  55.     if turn == n:
  56.         return False
  57.     if num == n: num -= n 
  58.     block = blocks[num]
  59.     if num in put:
  60.         if num == put[-1]:
  61.             print("A", end = ' ')
  62.             ans, row, col = copy.deepcopy(pro[len(put)-1])
  63.             if num == turn:
  64.                 turn +=1
  65.             return polyomino(pro[:-1], ans, num+1,row,col,put[:-1],turn)
  66.         else:
  67.             print("B",end=" ")
  68.             return polyomino(pro,ans,num+1,row,col,put,turn)
  69.     h,w = block[0]
  70.     print(num,"w=%d, h=%d"%(col,row))
  71.     print(put)
  72.     if row+h > side:
  73.         print("C",end = " ")
  74.         return polyomino(pro,ans,num+1,row,col,put,turn)
  75.     else:
  76.         start = 0 if col+1-w <= 0 else col+1-w
  77.         result = puzzle(num,ans,row,start)
  78.         while result == False and start+w < side  :
  79.             start += 1
  80.             result = puzzle(num,ans,row,start)
  81.         if result == False:
  82.             print("D",end = " ")
  83.             return polyomino(pro,ans,num+1,row,col,put,turn)
  84.         else:
  85.             put.append(num)
  86.             pro.append(result)
  87.             ans, row, col = result
  88.             print("E")
  89.             print(result)
  90.             return polyomino(pro,ans, num+1,row,col,put,turn)
  91.  
  92. #---------------------------------------------------------------------------------#    
  93. side = check(count)        #the side of the panel
  94. if side == False:
  95.     print("No solution possible")
  96. else:
  97.     process = []
  98.     answer = np.zeros([side,side], dtype="i").tolist()
  99.     process.append([copy.deepcopy(answer),0,0])
  100.     answer = polyomino(process,answer)
  101.     if answer == False:
  102.         print("No solution possible")
  103.     else:
  104.         for line in answer:
  105.             print(' '.join(map(str, line)))
  106.  
Success #stdin #stdout 0.2s 27200KB
comments (?)
stdin
copy 
3
3 2
1 1
0 1
0 1
2 1
1 
1
3 1
1 
1
1
stdout
copy 
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
0 w=0, h=0
[]
E
[[[1, 1, 0], [0, 1, 0], [0, 1, 0]], 0, 2]
[[1, 1, 0], [0, 1, 0], [0, 1, 0]]
1 w=2, h=0
[0]
E
[[[1, 1, 2], [0, 1, 2], [0, 1, 0]], 1, 0]
[[1, 1, 2], [0, 1, 2], [0, 1, 0]]
2 w=0, h=1
[0, 1]
C [[1, 1, 2], [0, 1, 2], [0, 1, 0]]
B [[1, 1, 2], [0, 1, 2], [0, 1, 0]]
A [[1, 1, 0], [0, 1, 0], [0, 1, 0]]
2 w=2, h=0
[0]
E
[[[1, 1, 3], [0, 1, 3], [0, 1, 3]], 1, 0]
[[1, 1, 3], [0, 1, 3], [0, 1, 3]]
B [[1, 1, 3], [0, 1, 3], [0, 1, 3]]
1 w=0, h=1
[0, 2]
E
[[[1, 1, 3], [2, 1, 3], [2, 1, 3]], 2, 2]
[[1, 1, 3], [2, 1, 3], [2, 1, 3]]
1 1 3
2 1 3
2 1 3
https://ideone.com/wZZSQR
language:
Python 3 nbc (python 3.7.3)
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!