Cakeminator · Interview Problem

Codeforces

Easy

Arrays

Matrices

Simulation

Greedy

Cakeminator

Count how many cakes can be eaten from a grid after repeatedly taking whole rows or columns that contain no strawberries.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given an $n \times m$ grid representing a cake. Each cell is either empty or contains a strawberry.

You may eat any row that contains no strawberries, and you may eat any column that contains no strawberries. When you eat a row or column, every cell in that row or column is removed.

Your task is to find the maximum number of cells that can be eaten.

Clarification

A cell can be eaten if it belongs to at least one chosen row or chosen column. Rows and columns are independent choices, but you can only choose rows/columns that contain no strawberries in the original grid.

Input Format

The first line contains two integers $n$ and $m$ .

The next $n$ lines each contain a string of length $m$ describing the grid.

. means an empty cell
S means a strawberry

Output Format

Print one integer: the maximum number of cells that can be eaten.

Constraints

Assume $1 \le n, m \le 100$ .

The grid contains only . and S.

Examples

Sample cases returned by the problem API.

Example 1

Input

3 4
.S..
....
S.S.

Output

Explanation

Row 2 has no strawberries, so all 4 cells in that row can be eaten. Column 4 also has no strawberries, adding 1 more new cell from row 1/3 intersections. Total = 5.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress