FPC21-002.Distribution Center
Easy · 1 s · 256 MB
- icpc
- fpc
- 2021
Sokoban is the best employee at your town's biggest distribution center. He likes his job because it is simple, albeit a bit physically intensive. Everyday he is pushing crates to some possbile destinations from where they will be loaded in trucks. Unfortunately, Sokoban's youth is behind him, so he starts to feel the effects of the physical labour. Therfore, he came up with an algorithm to help him move the crates optimally: the Fast Pushing Crates (FPC) algorithm. For the algorithm to be complete, he needs a bit of help from you.
His algorithm receives as input the layout of the distribution center, as a grid, and returns the steps he needs to take to efficiently push the crates. In his algorithm, he needs to find out which squares in the grid are dead squares. We call a square a dead square if it is a wall or if it is impossible to push a crate from that square to any of the destinations (even if Sokoban could teleport to any location).
Given the layout of the distribution center, help Sokoban find out which squares are dead squares.
Giriş formatı
The input consists of:
• A line with two integers and (), the number of rows and columns of the grid.
• lines, each containing characters, where:
• A ‘#’ represents a wall. It is guaranteed that the grid is surrounded by walls.
• A ‘D’ represents a destination. There can be any number of them, including .
• A ‘.’ represents an empty square.
Çıxış formatı
Output lines, each containing characters, where the th character of the th line is:
• ‘X’ if the square at position is a dead square.
• ‘O’ otherwise.
Qeyd
Source: Freshmen Programming Contest 2021 · Author: Alin Dondera · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 7 of the 26 original test cases (the largest) are omitted here to keep the problem lightweight.
Nümunələr
Giriş #1
7 7 ####### #.....# #.....# #..D..# #.....# #.....# #######
Çıxış #1
XXXXXXX XXXXXXX XXOOOXX XXOOOXX XXOOOXX XXXXXXX XXXXXXX
Giriş #2
8 8 ######## #..#D### #..#.### #..#.### #..#...# #..#.### #D.#.### ########
Çıxış #2
XXXXXXXX XXXXOXXX XOXXOXXX XOXXOXXX XOXXOOXX XOXXOXXX XOXXXXXX XXXXXXXX