SRM623 Div1 Easy "UniformBoard"
問題
TopCoder Statistics - Problem Statement
訳
N * Nのマスを持つ正方形のボードがある。いくつかのマスには何も乗っていない。その他のマスにはりんごか梨が乗っている。あなたはボードの現在の状態がString配列 boardとして与えられる。boardにおいて、'.'は何も乗っていない空のマスで、'A'はりんご、'P'は梨が乗っていることを示す。
あなたはK回まで、ある操作をすることができる。その操作とは、1つのフルーツ(りんごか梨)をつまみ上げ、任意の空のマスに置くことである。(フルーツを置くマスは、元のマスと隣り合っていなくてもよい)フルーツをボードの外に置くことはできず、フルーツを置くことができるのはボード上のマスだけである。
りんごが置かれたマスだけで構成された長方形を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; } };