192. Knight's Move

Codeforces

IDCF10269192

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have an 8 by 8 chessboard with several knights on it. The chessboard has no other pieces on it. Given the positions of the knights, find all of the spaces that the knights can travel to in a single move. Recall that in chess, a knight can move exactly 2 spaces in one direction, and exactly one space in a perpendicular direction. For example, a knight could move 2 spaces left and 1 space up, or 2 spaces up and 1 space left, but a knight could not move 2 spaces left on its own, or 1 space up and 1 space right, for example. The input consists of 8 lines, each consisting of 8 characters, representing the chessboard. A single dot (".") represents an empty space on the chessboard, and an uppercase K ("K") represents the position of a knight. Output 8 lines, in the same format as the input, except, replace each empty space that can be moved to by at least one knight in a single move with an asterisk ("*"). ## Input The input consists of 8 lines, each consisting of 8 characters, representing the chessboard.A single dot (".") represents an empty space on the chessboard, and an uppercase K ("K") represents the position of a knight. ## Output Output 8 lines, in the same format as the input, except, replace each empty space that can be moved to by at least one knight in a single move with an asterisk ("*"). [samples]

**Definitions** Let $ B \in \{ \text{`.`}, \text{`K`} \}^{8 \times 8} $ be the input chessboard, where $ B[i][j] = \text{`K`} $ denotes a knight at row $ i $, column $ j $ (0-indexed). Let $ N = \{ (\pm 2, \pm 1), (\pm 1, \pm 2) \} $ be the set of 8 possible knight move vectors. **Constraints** - $ i, j \in \{0, 1, \dots, 7\} $ for all board positions. - Knights are only on squares where $ B[i][j] = \text{`K`} $. **Objective** Construct output board $ O \in \{ \text{`.`}, \text{`K`} , \text{`*`} \}^{8 \times 8} $ such that: - $ O[i][j] = \text{`K`} $ if $ B[i][j] = \text{`K`} $, - $ O[i][j] = \text{`*`} $ if $ B[i][j] = \text{`.`} $ and $ \exists (di, dj) \in N $ such that $ (i - di, j - dj) \in [0,7]^2 $ and $ B[i - di][j - dj] = \text{`K`} $, - $ O[i][j] = \text{`.`} $ otherwise.

API Response (JSON)

{
  "problem": {
    "name": "192. Knight's Move",
    "description": {
      "content": "You have an 8 by 8 chessboard with several knights on it. The chessboard has no other pieces on it. Given the positions of the knights, find all of the spaces that the knights can travel to in a singl",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269192"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have an 8 by 8 chessboard with several knights on it. The chessboard has no other pieces on it. Given the positions of the knights, find all of the spaces that the knights can travel to in a singl...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ B \\in \\{ \\text{`.`}, \\text{`K`} \\}^{8 \\times 8} $ be the input chessboard, where $ B[i][j] = \\text{`K`} $ denotes a knight at row $ i $, column $ j $ (0-indexed).  \n\nLet $ N = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments