 # USACO Bull in a China Shop (Bronze) Solution

May 27th, 2022
1,406
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from sys import exit
2.
5.     # First piece in this array is the one we're trying to match to
6.     pieces = []
7.     sides = []
8.     for i in range(k + 1):
9.         top = n - 1
10.         bottom = 0
11.         left = n - 1
12.         right = 0
13.         piece = [[False for _ in range(n)] for _ in range(n)]
14.
15.         for r in range(n):
17.             for c in range(n):
18.                 piece[r][c] = row[c] == '#'
19.                 if piece[r][c]:
20.                     bottom = max(bottom, r)
21.                     top = min(top, r)
22.                     left = min(left, c)
23.                     right = max(right, c)
24.
25.         pieces.append(piece)
26.         sides.append((left, right, top, bottom))
27.
28.
29. def check(piece: [[bool]], x: int, y: int) -> bool:
30.     """checks if a piece location is in bounds and is '#'"""
31.     return 0 <= x < len(piece) and 0 <= y < len(piece[x]) and piece[x][y]
32.
33.
34. target = pieces
35. # Try all the pieces & shifts to find the correct one
36. for i in range(1, k + 1):
37.     for j in range(1, k + 1):
38.         for idx in range(sides[i] - n + 1, sides[i] + 1):
39.             for idy in range(sides[i] - n + 1, sides[i] + 1):
40.                 for jdx in range(sides[j] - n + 1, sides[j] + 1):
41.                     for jdy in range(sides[j] - n + 1, sides[j] + 1):
42.                         good = True
43.                         for x in range(n):
44.                             for y in range(n):
45.                                 ipiece = check(pieces[i], x + idx, y + idy)
46.                                 jpiece = check(pieces[j], x + jdx, y + jdy)
47.                                 # two '#' are in the same place
48.                                 if ipiece and jpiece:
49.                                     good = False
50.                                     break
51.                                 # the result doesn't match the figurine
52.                                 if target[x][y] != (ipiece or jpiece):
53.                                     good = False
54.                                     break
55.
56.                             if not good:
57.                                 break
58.
59.                         if good:
60.                             print(i, j, file=open('bcs.out', 'w'))
61.                             exit()
62.