I. I WIN

Codeforces

IDCF10020I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on the ends and I in the middle (that is, it spells WIN in some order). Of course the only possible triominoes are the one with three squares in a straight line and the L-shaped ones, and the triominoes can't overlap. First line contains two integers n and m with 1 ≤ m, n ≤ 22. The next n lines contain m characters each (only the letters W, I and N). Output a single integer: the maximum number of nonoverlapping WIN-triominoes. ## Input First line contains two integers n and m with 1 ≤ m, n ≤ 22. The next n lines contain m characters each (only the letters W, I and N). ## Output Output a single integer: the maximum number of nonoverlapping WIN-triominoes. [samples]

**Definitions** Let $ n, m \in \mathbb{Z} $ with $ 1 \leq n, m \leq 22 $. Let $ G \in \{W, I, N\}^{n \times m} $ be a grid of characters. A **WIN-triomino** is a connected set of three unit squares forming either a straight line or an L-shape, such that the letters on the squares form the sequence $ W $, $ I $, $ N $ in some order, with $ I $ in the middle square (i.e., the central square of the triomino must be $ I $, and the two endpoints must be $ W $ and $ N $). **Constraints** 1. Triominoes must be axis-aligned or L-shaped (i.e., occupy three squares forming a straight line of length 3 or an L-tromino). 2. Triominoes must not overlap. 3. Each triomino must consist of exactly one $ W $, one $ I $, and one $ N $, with the $ I $ located at the center square of the triomino shape. **Objective** Maximize the number of non-overlapping WIN-triominoes that can be placed on $ G $.

API Response (JSON)

{
  "problem": {
    "name": "I. I WIN",
    "description": {
      "content": "Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10020I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\leq n, m \\leq 22 $.  \nLet $ G \\in \\{W, I, N\\}^{n \\times m} $ be a grid of characters.  \n\nA **WIN-triomino** is a connected set of three unit squ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments