H. Battleship

Codeforces

IDCF100H

Time2000ms

Memory64MB

Difficulty—

dfs and similarimplementation

English · Original

Chinese · Translation

Formal · Original

Do you know the game Battleship? If no, look into Wikipedia article http://en.wikipedia.org/wiki/Battleship_(game). You are given the positions of ships on a 10 × 10 board for playing Battleship. According to the rules, the board should contain the following ships: * one of size 4 (4 × 1 or 1 × 4 rectangle), * two of size 3 (3 × 1 or 1 × 3 rectangles), * three of size 2 (2 × 1 or 1 × 2 rectangles), * four of size 1 (1 × 1 rectangles). The ships should not 'bend', touch each other or overlap in any way. Each ship can be oriented horizontaly or verticaly. Your task is to check whether the given set of boards meets the given conditions. ## Input The first line contains number _n_ (1 ≤ _n_ ≤ 10) — the number of boards. Each board is described by 10 lines containing 10 characters each. The symbol "0" stands for an empty square and the symbol "*" stands for a square occupied by a ship. The descriptions of boards are separated with empty lines. ## Output Print _n_ lines YES or NO. Print the first word if the board meets the given conditions; otherwise print the second word. [samples]

你了解游戏《战舰》吗？如果不了解，请参阅维基百科文章 http://en.wikipedia.org/wiki/Battleship_(game)。给你一个 #cf_span[10 × 10] 的棋盘，上面摆放了《战舰》游戏中的舰船。根据规则，棋盘上应包含以下舰船：舰船不能“弯曲”，不能相互接触或重叠。每艘舰船只能水平或垂直放置。你的任务是检查给定的棋盘是否满足上述条件。第一行包含数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 10]) —— 棋盘的数量。每个棋盘由 10 行组成，每行包含 10 个字符。符号 "0" 表示空格，符号 "*" 表示被舰船占据的格子。各棋盘的描述之间用空行分隔。请输出 #cf_span[n] 行，每行为 YES 或 NO。如果棋盘满足条件，则输出第一个词；否则输出第二个词。 ## Input 第一行包含数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 10]) —— 棋盘的数量。每个棋盘由 10 行组成，每行包含 10 个字符。符号 "0" 表示空格，符号 "*" 表示被舰船占据的格子。各棋盘的描述之间用空行分隔。 ## Output 请输出 #cf_span[n] 行，每行为 YES 或 NO。如果棋盘满足条件，则输出第一个词；否则输出第二个词。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of boards, with $ 1 \leq n \leq 10 $. For each board $ b \in \{1, \dots, n\} $, let $ B_b \in \{0, *\}^{10 \times 10} $ be a 10×10 grid where $ B_b[i][j] = * $ denotes a ship cell and $ B_b[i][j] = 0 $ denotes an empty cell. **Constraints** A valid board must satisfy: 1. The board contains exactly: - One ship of length 4, - Two ships of length 3, - Three ships of length 2, - Four ships of length 1. 2. Each ship is a contiguous horizontal or vertical segment of exactly its specified length. 3. No two ships share a cell (no overlap). 4. No two ships are adjacent, even diagonally (i.e., for any two ship cells $ (i_1, j_1) $ and $ (i_2, j_2) $ from different ships, $ \max(|i_1 - i_2|, |j_1 - j_2|) \geq 2 $). **Objective** For each board $ b \in \{1, \dots, n\} $, output: $$ \begin{cases} \text{YES} & \text{if } B_b \text{ satisfies all constraints}, \\ \text{NO} & \text{otherwise}. \end{cases} $$

Samples

Input #1

Output #1

YES
NO

API Response (JSON)

{
  "problem": {
    "name": "H. Battleship",
    "description": {
      "content": "Do you know the game Battleship? If no, look into Wikipedia article http://en.wikipedia.org/wiki/Battleship_(game). You are given the positions of ships on a 10 × 10 board for playing Battleship. Acco",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF100H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Do you know the game Battleship? If no, look into Wikipedia article http://en.wikipedia.org/wiki/Battleship_(game). You are given the positions of ships on a 10 × 10 board for playing Battleship. Acco...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你了解游戏《战舰》吗？如果不了解，请参阅维基百科文章 http://en.wikipedia.org/wiki/Battleship_(game)。给你一个 #cf_span[10 × 10] 的棋盘，上面摆放了《战舰》游戏中的舰船。根据规则，棋盘上应包含以下舰船：\n\n舰船不能“弯曲”，不能相互接触或重叠。每艘舰船只能水平或垂直放置。你的任务是检查给定的棋盘是否满足上述条件。\n\n第一行包含数字 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of boards, with $ 1 \\leq n \\leq 10 $.  \nFor each board $ b \\in \\{1, \\dots, n\\} $, let $ B_b \\in \\{0, *\\}^{10 \\times 10} $ be a 10×10 grid where...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments