I. Mason's Mark

Codeforces
IDCF10246I
Time4000ms
Memory256MB
Difficulty
English · Original
Formal · Original
You are given a rectangular matrix representing a picture made by Peter. The '#' character represents a black pixel and the '.' character a white pixel. You should count how many stones are on the picture with the respective letters A, B, and C. The first line contains two integers $W$ and $H$. The next $H$ lines each contain a string of length $W$. The strings are composed of '.' and '#'. *Limits* The output should consist of a single line, whose content is three integers $A$, $B$, and $C$ separated with single spaces, indicating the number of stones with the respective marks A, B, and C. *Sample Explanation* There are black pixels forming a letter C. These pixels, however, belong to the region around the stones and do not form a mark since they are not surrounded by white pixels. ## Input The first line contains two integers $W$ and $H$. The next $H$ lines each contain a string of length $W$. The strings are composed of '.' and '#'.*Limits* $7 <= W <= 1000$; $9 <= H <= 1000$. ## Output The output should consist of a single line, whose content is three integers $A$, $B$, and $C$ separated with single spaces, indicating the number of stones with the respective marks A, B, and C. [samples] ## Note *Sample Explanation*There are black pixels forming a letter C. These pixels, however, belong to the region around the stones and do not form a mark since they are not surrounded by white pixels.
**Definitions** Let $ W, H \in \mathbb{Z}^+ $ denote the width and height of the matrix. Let $ M \in \{ \text{`.`}, \text{`#`} \}^{H \times W} $ be the binary matrix representing the picture, where `#` denotes a black pixel and `.` denotes a white pixel. Let $ R \subseteq \{ (i,j) \mid 1 \le i \le H, 1 \le j \le W \} $ be the set of all connected components of black pixels under 4-directional connectivity (up, down, left, right). For each connected component $ c \in R $, define its **bounding box** as the minimal axis-aligned rectangle enclosing all pixels in $ c $. Define a **stone** as a connected component $ c \in R $ such that: - All pixels in $ c $ are part of a **closed contour** forming one of the letters A, B, or C. - The contour is **fully surrounded by white pixels** (i.e., no black pixel touches the matrix boundary). - The shape of $ c $ matches the topological structure of one of the letters A, B, or C (as defined by standard pixel-based glyph recognition: A has a triangular top and a horizontal bar; B has two half-circles and a vertical bar; C is a concave curve open to the right). **Constraints** 1. $ 1 \le W, H \le 100 $ 2. Each connected component $ c \in R $ consists of at least 3 pixels. 3. Only components fully enclosed by white pixels (i.e., no pixel in $ c $ is on the matrix boundary) are considered valid stones. **Objective** Count the number of valid stone components matching the shapes of letters A, B, and C: Let $ A = |\{ c \in R \mid c \text{ matches shape A} \}| $, $ B = |\{ c \in R \mid c \text{ matches shape B} \}| $, $ C = |\{ c \in R \mid c \text{ matches shape C} \}| $. Output: $ A \ B \ C $
API Response (JSON)
{
  "problem": {
    "name": "I. Mason's Mark",
    "description": {
      "content": "You are given a rectangular matrix representing a picture made by Peter. The '#' character represents a black pixel and the '.' character a white pixel. You should count how many stones are on the pic",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10246I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a rectangular matrix representing a picture made by Peter. The '#' character represents a black pixel and the '.' character a white pixel. You should count how many stones are on the pic...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ W, H \\in \\mathbb{Z}^+ $ denote the width and height of the matrix.  \nLet $ M \\in \\{ \\text{`.`}, \\text{`#`} \\}^{H \\times W} $ be the binary matrix representing the picture, wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments