199. Plane Tour

Codeforces

IDCF10269199

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Your team solved all of the problems at CodeQuest 2021, and as a reward, the supervisors of the competition decided to show your team a room full of new aircraft (CodeQuest is run by Lockheed Martin, which builds airplanes and helicopters at their Owego, NY site, which the CodeRams attend every year). Once your team is dropped off in a room, the CodeQuest supervisors will let your team travel around the room and look at all of the new airplanes and helicopters. However, there are different rooms, and some of them are separated by impassable walls and locked doors. Since your team performed so well in the CodeQuest competition, the supervisors let your team choose which room to tour. You can only go in one room during the tour. Your task is to figure out the maximum number of aircraft that you can see, if you visit the optimal room on your team's private tour. The Lockheed Martin facility that the competition is taking place at can be represented as a 2D grid. The first line of input contains two space-separated integers $n$ and $m$: the number of rows and columns of the grid representation of the facility, respectively. The next $n$ lines each contain $m$ characters: the 2D top-down view representation of the Lockheed Martin facility. If a character is a single dot ("."), then the space in the grid is empty space that can be walked through. If a character is an x ("X"), then the space in the grid is an impassable wall. If a character is a p ("P"), then the space in the grid is an airplane or helicopter. Note that you can walk through a space with an aircraft. You cannot walk diagonally. Output a single positive integer $p$: the maximum number of aircraft that you can see on your facility tour, only visiting one room. ## Input The Lockheed Martin facility that the competition is taking place at can be represented as a 2D grid. The first line of input contains two space-separated integers $n$ and $m$: the number of rows and columns of the grid representation of the facility, respectively.The next $n$ lines each contain $m$ characters: the 2D top-down view representation of the Lockheed Martin facility. If a character is a single dot ("."), then the space in the grid is empty space that can be walked through. If a character is an x ("X"), then the space in the grid is an impassable wall. If a character is a p ("P"), then the space in the grid is an airplane or helicopter. Note that you can walk through a space with an aircraft.You cannot walk diagonally. ## Output Output a single positive integer $p$: the maximum number of aircraft that you can see on your facility tour, only visiting one room. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the grid. Let $ G \in \{., X, P\}^{n \times m} $ be the grid representation, where: - $ G[i][j] = '.' $: walkable empty space, - $ G[i][j] = 'X' $: impassable wall, - $ G[i][j] = 'P' $: aircraft (walkable). A *room* is a maximal connected component of walkable cells (using 4-directional connectivity: up, down, left, right), excluding walls. **Constraints** 1. $ 1 \leq n, m \leq 100 $ 2. Each cell is in $ \{., X, P\} $ **Objective** Find the maximum number of aircraft ('P') in any single connected room: $$ \max_{\text{room } R} \left| \{ (i,j) \in R \mid G[i][j] = 'P' \} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "199. Plane Tour",
    "description": {
      "content": "Your team solved all of the problems at CodeQuest 2021, and as a reward, the supervisors of the competition decided to show your team a room full of new aircraft (CodeQuest is run by Lockheed Martin, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269199"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your team solved all of the problems at CodeQuest 2021, and as a reward, the supervisors of the competition decided to show your team a room full of new aircraft (CodeQuest is run by Lockheed Martin, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid.  \nLet $ G \\in \\{., X, P\\}^{n \\times m} $ be the grid representation, where:  \n- $ G[i][j] = '.' $: walkable empty spa...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments