SRM494 - div2 - level two

srm494_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM494 - div2 - level two

Normally Mr. Grey is not a painter, but he recently had 
an absolutely brilliant idea for a picture. He thinks 
that once drawn, it will bring him world-wide fame.

The picture will be painted on an NxM sheet of white paper 
consisting of 1x1 squares. Its rows are numbered from 0 to 
N-1 and the columns are numbered from 0 to M-1. The cell in 
row i, column j is denoted as (i, j).

Of course, Mr. Grey already has a picture plan in his mind. 
It is given in a String[] picture, which contains exactly 
N elements, where each element contains exactly M characters. 
character j in element i of picture will be 'B' if the 
cell (i, j) must be painted black, and it will be 'W' 
if this cell must be left white.

Mr. Grey has a lot of black paint, but unfortunately he 
doesn't have a brush, so he went to a local shop to buy one. 
The shop offers square brushes of different sizes. 
More exactly, for each positive integer S, one can buy an 
SxS brush in the shop. Using an SxS brush, Mr. Grey will 
be able to paint entirely black SxS squares on the sheet 
of paper. In other words, he can choose row R and column 
C such that 0 <= R <= N - S, 0 <= C <= M - S, and then 
paint all cells (r, c) such that R <= r < R + S and 
C <= c < C + S in black paint. He can repeat this operation 
infinitely many times. If a cell must be black according to 
picture, it may be painted black several times. However, 
if a cell must be white, then it must never be painted black.

It's easy to see that every picture can be drawn using a 
1x1 brush, but it will be impossible to draw some pictures 
using larger brushes. Buying a 1x1 brush seems to be the 
most practical choice. However, Mr. Grey is sure that big 
masters must use big brushes. Therefore, he would like to 
buy the largest possible brush that will still allow him 
to draw the picture that he has in mind.

Return the maximum value of S such that it's possible 
to draw picture using a brush of size SxS.

Definition:
    Class: Painting
    Method: largestBrush
    Parameters: String[]
    Returns: int
    Method signature: int largestBrush(String[] picture)
"""

class Painting(object):
    """Colorful Cards

    Constraints:
        - picture will contain between 1 and 50 elements, 
          inclusive.
        - Each element of picture will contain between 
          1 and 50 characters, inclusive.
        - All elements of picture will contain the same 
          number of characters.
        - Each character in picture will be 'B' or 'W'.
        - There will be at least one 'B' character in picture.

    >>> painting = Painting()
    >>> print painting.largestBrush(
    ...     ["BBBB", "BBBB", "BBBB", "BBBB", ])
    4
    >>> print painting.largestBrush(
    ...     ["BBBB", "BWWB", "BWWB", "BBBB", ])
    1
    >>> print painting.largestBrush(
    ...     ["WBBBBB", "BBBBBB", "BBBBBB", "BBBBBB", ])
    3
    >>> print painting.largestBrush(
    ...     ["BBBB", "BBBB", "WBBB", "BBBB", "BBBB", "BBBB", ])
    2
    >>> print painting.largestBrush(
    ...     ["WBBBBBWWWWWWWWW", "WBBBBBBWWWWWWWW", "WBBBBBBBBBBBWWW", 
    ...     "WBBBBBBBBBBBWWW", "BBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBB", 
    ...     "BBBBBBBBBBBBBBB", "BBBBBBBBWWBBBBB", "BBBBBBBBWBBBBBB", 
    ...     "WBBBBBBBWBBBBBW", "BBBBBBBWWBBBBBW", "BBBBBBBWWBBBBBW", 
    ...     "BBBBBBWWWBBBBBW", "BBBBBWWWWWWWWWW", "BBBBBWWWWWWWWWW", ])
    5
    """

    def __init__(self):
        pass

    def largestBrush(self, picture=[]):
        def check(max, pic):
            my = 0
            while my <= len(pic) - max:
                mx = 0
                while mx <= len(pic[0]) - max:
                    line = ''.join([l[mx:mx+max] for l in pic[my:my+max]])
                    if 'W' not in line:
                        for y in range(max):
                            pic[my+y] = pic[my+y][:mx] \
                                    + 'C'*max + pic[my+y][mx+max:]
                    mx += 1
                my += 1
            return 'B' not in ''.join([l for l in pic])

        max = min([len(picture), len(picture[0])])
        for i in [max - m for m in range(max - 1)]:
            if check(i, picture[:]):
                return i
        return 1

if __name__ == '__main__':
    import doctest
    doctest.testmod()