SRM623 Div1 Easy "UniformBoard"

問題

TopCoder Statistics - Problem Statement

訳

N * Nのマスを持つ正方形のボードがある。いくつかのマスには何も乗っていない。その他のマスにはりんごか梨が乗っている。あなたはボードの現在の状態がString配列 boardとして与えられる。boardにおいて、'.'は何も乗っていない空のマスで、'A'はりんご、'P'は梨が乗っていることを示す。

あなたはK回まで、ある操作をすることができる。その操作とは、１つのフルーツ（りんごか梨）をつまみ上げ、任意の空のマスに置くことである。（フルーツを置くマスは、元のマスと隣り合っていなくてもよい）フルーツをボードの外に置くことはできず、フルーツを置くことができるのはボード上のマスだけである。

りんごが置かれたマスだけで構成された長方形をuniform rectangleと呼ばれる。あなたがフルーツに対し操作を行った後に、なるべく大きなuniform rectangleを作りたい。最大の面積を持つuniform rectangleの、その面積を返せ。なお、りんごが全くなければ0を返せ。

制約

1 <= N <= 20
0 <= K <= 1000

考えたこと

すみません。カンニングしちゃいました。

2014-06-05 - kojingharangの日記 - TopCoder部
コチラを参考にしましたm(_ _)m

.が一個だけあれば自由というのが問題のキモ

ソースコード

class UniformBoard {
public:

    int getBoard(vector <string> board, int K) {
        int N = board.size();

        int AN = 0;
        bool dot = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'A') AN++;
                if (board[i][j] == '.') dot = true;
            }
        }

        int best = 0;
        for (int y1 = 0; y1 < N; y1++) for (int y2 = y1; y2 < N; y2++) {
            for (int x1 = 0; x1 < N; x1++) for (int x2 = x1; x2 < N; x2++) {
                int ylen = y2 - y1 + 1;
                int xlen = x2 - x1 + 1;
                int area = ylen * xlen;
                if (AN < area) continue;
                int cost = 0;
                for (int y = y1; y <= y2; y++) {
                    for (int x = x1; x <= x2; x++) {
                        if (board[y][x] == '.') cost += 1;
                        if (board[y][x] == 'P') cost += 2;
                    }
                }
                if (cost == 0 || (cost <= K && dot)) {
                    best = max(best, area);
                }
            }
        }
        
        return best;
    }
};