Piglets and Wolves
InterviewTime limit1sMemory limit256 MB
Given an N by M grid with grassland, ice, mountains and wolf starts, simulate wolf sliding on ice and mark unreachable grassland cells as P.
- Level
Medium6 of 10
- Topics
- Simulation, BFS, Graph, Implementation
- Solved
- No attempts yet
Problem
Three piglet brothers live in a ring basin surrounded by mountains, and they want to leave their mother and build a new house.
The ring basin can be represented as a two-dimensional grid of size N × M, and the terrain of each cell is one of grassland, ice, or mountain.
Not only pig families but also wolves live in the ring basin. A wolf can move from a cell to a vertically or horizontally adjacent cell that is not a mountain. If the cell it moves into is ice, the wolf slides in the direction it moved until it steps on grassland or hits a mountain. If it hits a mountain, the wolf can stand still on the ice and then move again in another direction.
Because the lazy piglets plan to build their house out of straw, a wolf that reaches the cell containing the house can break in with ease. A cell that wolves living in the ring basin cannot reach and whose terrain is grassland is called a 'safe spot.' Given a map of the ring basin, mark the locations of all safe spots on the map for the lazy piglets.
Input
The first line gives N (3 ≤ N ≤ 100), the number of rows of the grid, and M (3 ≤ M ≤ 100), the number of columns of the grid.
The next N lines give strings of length M describing the map.
The j-th character of the (i+1)-th line indicates the terrain type of the i-th row and j-th column: '.' for grassland, '+' for ice, '#' for mountain, and 'W' means a wolf lives there. There can be multiple cells with wolves, and the terrain of a cell with a wolf is always grassland. The first and N-th rows and the first and M-th columns of the map are always mountains.
Output
Print the map given as input, replacing every grassland cell where a piglet can live with the character 'P'.