Connection Status:
Competition Arena > AmoebaDivTwo

AmoebaDivTwo

SRM 493 · 2010-11-01 · by K.A.D.R

SRM 493 · 2010-11-01 · by K.A.D.R · Brute Force, Simple Search, Iteration
Class Name: AmoebaDivTwo
Return Type: int
Method Name: count
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Little Romeo likes cosmic amoebas a lot. Recently he received one as a gift from his mother. He decided to place his amoeba on a rectangular table. The table is a grid of square 1x1 cells, and each cell is occupied by either matter or antimatter. The amoeba is a rectangle of size 1xK. Romeo can place it on the table in any orientation as long as every cell of the table is either completely covered by part of the amoeba or completely uncovered, and no part of the amoeba lies outside of the table. It is a well-known fact that cosmic amoebas cannot lie on top of matter, so every cell of the table covered by the amoeba must only contain antimatter.


You are given a String[] table, where the j-th character of the i-th element is 'A' if the cell in row i, column j of the table contains antimatter or 'M' if it contains matter. Return the number of different ways that Romeo can place the cosmic amoeba on the table. Two ways are considered different if and only if there is a table cell that is covered in one but not the other.

Constraints

  • table will contain between 1 and 50 elements, inclusive.
  • Each element of table will contain between 1 and 50 characters, inclusive.
  • All elements of table will have the same length.
  • Each character of each element of table will be either 'A' or 'M'.
  • K will be between 1 and 50, inclusive.
Examples
0)
{"MA"}
2
Returns: 0

The amoeba requires a 1x2 or 2x1 rectangle containing only antimatter, but there is no such space available on the table.

1)
{"AAA",
 "AMA",
 "AAA"}
3
Returns: 4
2)
{"AA",
 "AA",
 "AA"}
2
Returns: 7

Here are all 7 configurations, where X represents the amoeba: XX .. .. X. .X .. .. .. XX .. X. .X X. .X .. .. XX .. .. X. .X

3)
{"MMM",
 "MMM",
 "MMM"}
1
Returns: 0

There are no cells with antimatter at all.

4)
{"A"}
1
Returns: 1

Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AmoebaDivTwo with a public method int count(vector<string> table, int K) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous