Boundless Boxes

Remember the painter Peer from the 2008 ACM ICPC World Finals? (Aside from the artist Peer, this problem does not have anything to do with the World Finals problem, so do not worry if you were not there or have not read that problem. In fact, any knowledge of the referenced problem will not help you solve this one!) Peer was one of the inventors of monochromy, meaning each painting has a single color, but in different shades. He also believed in simple geometric forms. Several months ago, Peer was painting triangles on canvas from the outside in. Now triangles are out of fashion, and squares are in. His latest paintings use concentric squares, created from the inside out! Peer starts on a rectangular canvas divided into a perfect square grid. He picks a number of single grid cells as central seeds and paints them with the darkest shade. For each seed square, Peer paints a larger square using a lighter shade to enclose it, and repeats with larger squares to enclose the previous ones, until the entire canvas is covered. Each square is exactly one grid cell larger and one shade lighter than the one it encloses. When squares overlap, a grid cell is always filled using the darker shade. Once Peer decides where to place the seeds, the only remaining challenge is to determine how many different shades of the color are required. To help Peer, you must write a program that computes the number of shades needed for such a painting, given the size of the canvas and the locations of the seed squares.