88 lines
2.7 KiB
Markdown
88 lines
2.7 KiB
Markdown
# B. Осыпающийся песок
|
||
|
||
Динозавр Дино решил почистить свой террариум от камней с помощью магнита. В террариуме находятся песок и камни, которые магнитятся магнитом. Нужно написать функцию, которая бы вынимала все камешки магнитом и оставила бы только песок.
|
||
|
||
## Формат ввода
|
||
|
||
- В первой строке - высота террариума `h` (`1 <= h <= 10^6`);
|
||
- Во второй строке - ширина террариума `w` (`1 <= w <= 10^6`);
|
||
- Далее задается двумерный массив `h x v` <= `10^6` (террариум), состоящий из песчинок (символы `0`) и камешков (символы `x`);
|
||
|
||
## Формат вывода
|
||
|
||
Вывести получившийся двумерный массив `h x w` (`1 <= h <= 10^6, 1 <= w <= 10^6`), который будет состоять из песчинок (символ `0`) и пустых ячеек (символ `-`)
|
||
|
||
## Пример 1
|
||
|
||
Ввод
|
||
|
||
```
|
||
4
|
||
5
|
||
0 0 0 0 x
|
||
0 x x 0 0
|
||
0 x 0 x 0
|
||
x 0 0 x 0
|
||
```
|
||
|
||
Вывод
|
||
|
||
```
|
||
- - - - -
|
||
0 0 0 - -
|
||
0 0 0 0 0
|
||
0 0 0 0 0
|
||
```
|
||
|
||
## Пример 2
|
||
|
||
Ввод
|
||
|
||
```
|
||
3
|
||
5
|
||
x x x x x
|
||
0 x x 0 0
|
||
x x x x x
|
||
```
|
||
|
||
Вывод
|
||
|
||
```
|
||
- - - - -
|
||
- - - - -
|
||
0 - 0 0 -
|
||
```
|
||
|
||
## Пример 3
|
||
|
||
Ввод
|
||
|
||
```
|
||
3
|
||
5
|
||
x x x x x
|
||
x x x x x
|
||
x x x x x
|
||
```
|
||
|
||
Вывод
|
||
|
||
```
|
||
- - - - -
|
||
- - - - -
|
||
- - - - -
|
||
```
|
||
|
||
## Примечание
|
||
|
||
Камешки вытаскиваются постепенно слева направо. Пока все камешки не убраны из текущего столбца - Дино не переводит магнит на следующий столбец.
|
||
|
||
Камешки вытаскиваются сверху вниз (от самого верхнего до самого нижнего) по следующим правилам:
|
||
|
||
- песчинки могут двигаться только вниз;
|
||
- песчинки не перемещаются наверх даже при движении камешков наверх (считать, что камешки двигаются вверх сквозь песчинки);
|
||
- все песчинки под действием гравитации падают вниз в своем столбце;
|
||
- песчинки из соседних столбцов слева и справа падают в текущий столбик, если разница в высоте - больше единицы;
|
||
- сначала падают песчинки справа, потом слева в текущую ячейку.
|