Advertisement
SansPapyrus683

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.  
  3. with open('bcs.in') as read:
  4.     n, k = [int(i) for i in read.readline().split()]
  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):
  16.             row = read.readline()
  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[0]
  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][3] - n + 1, sides[i][2] + 1):
  39.             for idy in range(sides[i][1] - n + 1, sides[i][0] + 1):
  40.                 for jdx in range(sides[j][3] - n + 1, sides[j][2] + 1):
  41.                     for jdy in range(sides[j][1] - n + 1, sides[j][0] + 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.  
Advertisement
RAW Paste Data Copied
Advertisement