108. The Hall Of Mirrors

Codeforces

IDCF10269108

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The Hall Of Mirrors You are in a hall of mirrors, and you shine a laser beam in a certain direction. Given the position of several diagonal mirrors, figure out the path of the laser beam. You shine your laser beam from the back of the hall of mirrors (on a computer screen, this will look like the "bottom" of the image). The first line of input contains two space-separated integers $n$, $m$, and $x$. $n$ and $m$ represent the number of rows and columns, respectively, and the number $x$ represents the index on the bottom row that you start shining the laser pointer at (with 0-based indices). The next $n$ lines contain $m$ characters representing the hall of mirrors. If a position does not contain a mirror, it will be pictured as a single dot. If it does have a mirror, it will be represented with either a forward slash ("/") or a backslash, which represents the direction that it reflects light in. See the example cases if you are confused on this. Output the given input matrix, however, replace any positions without a mirror that the laser pointer shines through horizontally with a hyphen, and replace any positions without a mirror that the laser pointer shines through vertically with a pipe ("|"), above the ENTER key on a keyboard. If the laser pointer travels through a space in both directions, replace the dot in that position with a plus symbol ("+"). ## Input The first line of input contains two space-separated integers $n$, $m$, and $x$. $n$ and $m$ represent the number of rows and columns, respectively, and the number $x$ represents the index on the bottom row that you start shining the laser pointer at (with 0-based indices). The next $n$ lines contain $m$ characters representing the hall of mirrors. If a position does not contain a mirror, it will be pictured as a single dot. If it does have a mirror, it will be represented with either a forward slash ("/") or a backslash, which represents the direction that it reflects light in. See the example cases if you are confused on this. ## Output Output the given input matrix, however, replace any positions without a mirror that the laser pointer shines through horizontally with a hyphen, and replace any positions without a mirror that the laser pointer shines through vertically with a pipe ("|"), above the ENTER key on a keyboard. If the laser pointer travels through a space in both directions, replace the dot in that position with a plus symbol ("+"). [samples]

**Definitions** Let $ n, m, x \in \mathbb{Z} $, where $ n $ is the number of rows, $ m $ is the number of columns, and $ x \in \{0, \dots, m-1\} $ is the 0-based starting column index on the bottom row. Let $ G \in \{ \text{`.`}, \text{`/`}, \text{`\`'} \}^{n \times m} $ be the grid representing the hall of mirrors. **Constraints** 1. $ 1 \leq n, m \leq 100 $ 2. $ 0 \leq x < m $ **Objective** Simulate the path of a laser beam starting at position $ (n-1, x) $, traveling upward (positive $ y $-direction), and reflecting upon encountering mirrors: - A `/` mirror reverses direction: $ (\Delta x, \Delta y) \mapsto (-\Delta y, -\Delta x) $ - A `\` mirror reverses direction: $ (\Delta x, \Delta y) \mapsto (\Delta y, \Delta x) $ Track the beam’s trajectory through empty cells (`.`), and annotate them as: - `\-` if traversed horizontally ($ \Delta x = \pm 1, \Delta y = 0 $) - `|` if traversed vertically ($ \Delta x = 0, \Delta y = \pm 1 $) - `+` if traversed in both directions Output the modified grid with annotations, leaving mirrors (`/`, `\`) unchanged.

API Response (JSON)

{
  "problem": {
    "name": "108. The Hall Of Mirrors",
    "description": {
      "content": "The Hall Of Mirrors You are in a hall of mirrors, and you shine a laser beam in a certain direction. Given the position of several diagonal mirrors, figure out the path of the laser beam. You shine ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269108"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Hall Of Mirrors\n\nYou are in a hall of mirrors, and you shine a laser beam in a certain direction. Given the position of several diagonal mirrors, figure out the path of the laser beam.\n\nYou shine ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, x \\in \\mathbb{Z} $, where $ n $ is the number of rows, $ m $ is the number of columns, and $ x \\in \\{0, \\dots, m-1\\} $ is the 0-based starting column index on the bottom ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments