USACO Bronze 2016 Open - Bull in a China Shop
Authors: Maggie Liu, David Zhang
We can loop through all possible pairs of pieces and shift them to check if they can make the original figurine. Since we cannot shift a piece so any '#' fall outside the grid, we need to find the sides of the pieces to determine how far to shift them.
Warning!
The official solution doesn't check if any '#' fall outside the grid.
As we iterate the pieces, we find the left, right, top and bottom sides of the piece and store them in the array. When we are shifting, we shift units to the left and units up, and shift units to the left and units up. This will send the piece at to and the piece at to . So, we see that must be bounded by and , and must be bounded by and , with and bounded similarly. Because of that, every '#' will fall inside the grid.
Once we have shifted the pieces, if there are two '#' in the same place, or if the result of superimposing the pieces is not the same as the original figurine (), then this shift will not work.
Implementation
Time Complexity:
C++
#include <cstdio>#include <iostream>#include <vector>using namespace std;bool check(int piece, int x, int y);int n;bool pieces[11][8][8];vector<int> s[11];int main() {
Java
import java.io.*;import java.util.*;public class BCS {public static boolean pieces[][][];public static int n;public static void main(String[] args) throws IOException {Kattio io = new Kattio("bcs");pieces = new boolean[11][8][8];
Python
from sys import exitwith open("bcs.in") as read:n, k = [int(i) for i in read.readline().split()]# First piece in this array is the one we're trying to match topieces = []sides = []for i in range(k + 1):top = n - 1bottom = 0
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!