Problem Brief

Push and Fall Boxes

You are given a matrix of characters representing a board. Each cell of the matrix contains one of three characters:

"." which means that the cell is empty;

"*" which means that the cell contains an obstacle;

"#" which means that the cell contains a box.

You decide to do the following operations:

Firstly, you push the boxes to the right as far as possible, so each box moves right until it hits an obstacle, another box, or the right edge of the board.

Then, you push the boxes down as far as possible, so each box moves down until it hits an obstacle, another box, or the bottom of the board.

Given board, a matrix representation of the board, your task is to return the state of the board after the push and fall operations.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than O(board.length * board[0].length * min(board.length, board[0].length)) will fit within the execution time limit.

1Example 1

Input

board = [['-', '#' , '-', '-' ,'-'], ['-', '-', '-', '-', '-'], ['#', '-', '#', '#', '-'], ['#', '-', '-', '-', '#']]

Output

['-', '-' , '-', '-' ,'-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['#', '-', '-', '-', '#']]

Explanation

After pushing the boxes to the right, the board state will be:

      [["#","#",".",".","*",".",".","#","."],
       [".",".",".",".",".",".","*",".","."],
       [".",".",".",".",".",".",".",".","."],
       ["#",".",".","#",".",".",".",".","#"]]

After pushing the boxes down, the board state will be:

      [[".",".",".",".","*",".",".",".","."],
       [".",".",".",".",".",".","*",".","."],
       [".",".",".",".",".",".",".",".","."],
       ["#","#","#","#",".",".",".","#","#"]]

2Example 2

Input

board = [["#",".",".",".",".",".",".",".","."], [".","#",".",".",".",".",".",".","."], [".",".","#",".",".",".",".",".","."], [".",".",".","#",".",".",".",".","."], [".",".",".",".","#",".",".",".","."], [".",".",".",".",".","#",".",".","."], [".",".",".",".",".",".","#",".","."], [".",".",".",".",".",".",".","#","."], ["*","*","*","*","*","*","*","*","#"]]

Output

[[".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], ["#",".",".",".",".",".",".",".","."], ["*","*","*","*","*","*","*","#","#"]]

Explanation

After pushing the boxes to the right, the board state will be:

      [["#",".",".",".",".",".",".",".","."],
       [".","#",".",".",".",".",".",".","."],
       [".",".","#",".",".",".",".",".","."],
       [".",".",".","#",".",".",".",".","."],
       [".",".",".",".","#",".",".",".","."],
       [".",".",".",".",".","#",".",".","."],
       [".",".",".",".",".",".","#",".","."],
       [".",".",".",".",".",".",".","#","."],
       ["*","*","*","*","*","*","*","*","#"]]

After pushing the boxes down, the board state will be:

      [[".",".",".",".",".",".",".",".","."],
       [".",".",".",".",".",".",".",".","."],
       [".",".",".",".",".",".",".",".","."],
       [".",".",".",".",".",".",".",".","."],
       [".",".",".",".",".",".",".",".","."],
       [".",".",".",".",".",".",".",".","."],
       ["#",".",".",".",".",".",".",".","."],
       ["*","*","*","*","*","*","*","#","#"]]