UniformBoard
SRM 623 · 2013-12-22 · by standy
SRM 623 · 2013-12-22 · by standy · Brute Force
Problem Statement
Problem Statement
A square board is divided into N rows by N columns of unit square cells.
Some cells of the board are empty.
Each of the other cells contains either an apple or a pear.
You are given the current state of the board as a String[] board.
In board, the character '.' denotes an empty cell, 'A' denotes an apple, and 'P' denotes a pear.
You are allowed to perform at most K moves. In each move, you can pick up one fruit (an apple or a pear) and place it onto any empty cell. (The new cell doesn't have to be adjacent to the old one.) Note that you cannot remove fruit from the board, you are only allowed to move it onto different cells.
A rectangular section of the board is called uniform if each cell in the rectangle contains an apple. After you are done moving the fruit, you want to have a uniform rectangle that is as large as possible somewhere on the board. Return the largest possible area of such a rectangle. If there are no apples, return 0.
You are allowed to perform at most K moves. In each move, you can pick up one fruit (an apple or a pear) and place it onto any empty cell. (The new cell doesn't have to be adjacent to the old one.) Note that you cannot remove fruit from the board, you are only allowed to move it onto different cells.
A rectangular section of the board is called uniform if each cell in the rectangle contains an apple. After you are done moving the fruit, you want to have a uniform rectangle that is as large as possible somewhere on the board. Return the largest possible area of such a rectangle. If there are no apples, return 0.
Constraints
- N will be between 1 and 20, inclusive.
- board will contain exactly N elements.
- Each element of board will contain exactly N characters.
- Each character in board will be '.', 'A', or 'P'.
- K will be between 0 and 1000, inclusive.
Examples
0)
{"AP",
".A"}
0
Returns: 1
You cannot move anything. The largest uniform rectangle on the board is a 1x1 rectangle that consists of a single cell with an apple.
1)
{"AP",
".A"}
1
Returns: 2
You are allowed to make one move. You can move one of the apples onto the currently empty cell, thus creating a 1x2 rectangle of apples.
2)
{"PPP",
"APA",
"A.P"}
2
Returns: 3
In two moves you can create a 1x3 rectangle of apples.
3)
{"AAA",
"PPP",
"AAA"}
10
Returns: 3
You are allowed to make at most 10 moves. However, you cannot make any moves because there are no empty cells.
4)
{"."}
1000
Returns: 0
Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class UniformBoard with a public method int getBoard(vector<string> board, int K) · 93 test cases · 2 s / 256 MB per case