FallingSand
SRM 661 · 2015-05-01 · by lg5293
Problem Statement
You have a rectangular board that is placed vertically. The board is divided into a grid of unit square cells. Some grid cells contain obstacles and some cells contain a grain of sand. All other cells are currently empty.
You are given the description of the board as a String[] board. The elements of board correspond to rows of the grid in the order from top to bottom. (E.g., board[0] represents the topmost row of cells.) Each character in each element of board represents one cell. The character 'x' represents a cell with an obstacle, 'o' is a grain of sand, and '.' (period) is an empty cell.
You would like to implement a simulation of falling sand. The rules are as follows:
- The obstacles don't move.
- Whenever there is an empty cell immediately below a grain of sand, the grain of sand moves into the empty cell.
Return the final configuration of the board after all grains of sand reach their final locations.
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element of board will have length between 1 and 50, inclusive.
- All elements of board will have the same length.
- Each character in each element of board will be one of 'x', 'o', and '.'.
{"ooooo",
"..x..",
"....x",
".....",
"....o"}
Returns: {"..o..", "..x.o", "....x", ".....", "oo.oo" }
The return value is: {"..o..", "..x.o", "....x", ".....", "oo.oo" }
{"..o..",
"..x.o",
"....x",
".....",
"oo.oo" }
Returns: {"..o..", "..x.o", "....x", ".....", "oo.oo" }
{"ooooxooo.ooxo.oxoxoooox.....x.oo"}
Returns: {"ooooxooo.ooxo.oxoxoooox.....x.oo" }
Nothing changes in this case, since all the sand is already at the bottom of the grid.
{"o",
".",
"o",
".",
"o",
".",
"."}
Returns: {".", ".", ".", ".", "o", "o", "o" }
{"oxxxxooo",
"xooooxxx",
"..xx.ooo",
"oooox.o.",
"..x....."}
Returns: {"oxxxxooo", "x.oo.xxx", "..xxo...", ".oo.x.o.", "ooxo.ooo" }
Note the final configuration of sand in the second column from the right. {"oxxxxooo", "x.oo.xxx", "..xxo...", ".oo.x.o.", "ooxo.ooo"}
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FallingSand with a public method vector<string> simulate(vector<string> board) · 50 test cases · 2 s / 256 MB per case