SRM623 Div1 Easy

UniformBoard.py

# -*- coding: utf-8 -*-
import math, string, itertools, fractions, heapq, collections, re, array, bisect

# .が１つもないのはk = 0と扱うと良い
class UniformBoard:
    def getBoard(self, board, K):
        N = len(board)
        dots, apples, pears = self.count(board)
        # print dots, apples, pears
        if dots == 0:
            K = 0

        table = [[0 for _ in xrange(N)] for _ in xrange(N)]

        for c in xrange(N):
            for r in xrange(N):
                total = 0
                if c != 0:
                    total += table[c - 1][r]
                if r != 0:
                    total += table[c][r - 1]
                if c != 0 and r != 0:
                    total -= table[c - 1][r - 1]
                table[c][r] = total + self.cost(board[c][r])

        maximum = 0
        for t in xrange(N):
            for b in xrange(t + 1):
                for r in xrange(N):
                    for l in xrange(r + 1):
                        cost = table[t][r]
                        if b != 0:
                            cost -= table[b - 1][r]
                        if l != 0:
                            cost -= table[t][l - 1]
                        if b != 0 and l != 0:
                            cost += table[b - 1][l - 1]

                        if cost <= K:
                            area = (t - b + 1) * (r - l + 1)
                            if area <= apples:
                                maximum = max(maximum, area)
        return maximum



    def cost(self, str):
        if str == "A":
            return 0
        if str == "P":
            return 2
        return 1

    def count(self, board):
        dots = 0
        apples = 0
        pears = 0
        for bo in board:
            for b in bo:
                if b == '.':
                    dots += 1
                if b == 'A':
                    apples += 1
                if b == 'P':
                    pears += 1
        return (dots, apples, pears)