You are running a gravity simulation involving falling boxes and exploding obstacles. The scenario is represented by a rectangular matrix of characters board.

Each cell of the matrix board 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.

The boxes all fall down simultaneously as far as possible, until they hit an obstacle, another grounded box, or the bottom of the board. If a box hits an obstacle, the box explodes, destroying itself and any other boxes within eight cells surrounding the obstacle. All the explosions happen simultaneously as well.

Given board, your task is to return the state of the board after all boxes have fallen.

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

Example

For

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

the output should be

solution(board) = [['-', '-', '-', '-', '*'],
                   ['-', '-', '-', '-', '-'],
                   ['-', '-', '-', '-', '-'],
                   ['-', '-', '-', '-', '-'],
                   ['-', '*', '-', '-', '#'],
                   ['#', '-', '*', '-', '#']]

Explanation:
Expand to see the example video.

Your browser does not support playing HTML5 video. You can instead.

Note: If you are not able to see the video, use this link to access it.

For

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

the output should be

solution(board) = [['-', '-', '*'],
                   ['-', '-', '*'],
                   ['-', '-', '*'],
                   ['-', '-', '-'],
                   ['*', '-', '-'],
                   ['*', '-', '#'],
                   ['*', '-', '#']]

Explanation:
Expand to see the example video.

Your browser does not support playing HTML5 video. You can instead.

Note: If you are not able to see the video, use this link to access it.

Input/Output

[execution time limit] 0.5 seconds (cpp)

[memory limit] 1 GB

[input] array.array.char board

A matrix that shows where the boxes and obstacles are located. The matrix consists only of characters '-', '*', and '#'.

Guaranteed constraints:
3 ≤ board.length ≤ 100,
3 ≤ board[i].length ≤ 100.

[output] array.array.char

Return a matrix representing the state of the board after all of the boxes have fallen.

Additional Test cases:

1) board: [["#","-","#","#","*"], ["#","-","-","#","#"], ["-","#","-","#","-"], ["-","-","#","-","#"], ["#","*","-","-","-"], ["-","-","*","#","-"]]

Expected return value

[["-","-","-","-","*"], ["-","-","-","-","-"], ["-","-","-","-","-"], ["-","-","-","-","-"], ["-","*","-","-","#"], ["#","-","*","-","#"]]

2) board: [["#","#","*"], ["#","-","*"], ["#","-","*"], ["-","#","#"], ["*","-","#"], ["*","-","-"], ["*","-","-"]]

Expected return value

[["-","-","*"], ["-","-","*"], ["-","-","*"], ["-","-","-"], ["*","-","-"], ["*","-","#"], ["*","-","#"]]

3) board: [["#","#","#","#"], ["-","#","-","#"], ["#","#","#","#"], ["-","-","-","-"], ["*","*","*","*"], ["-","-","-","-"]]

Expected return value

[["-","-","-","-"], ["-","-","-","-"], ["-","-","-","-"], ["-","-","-","-"], ["*","*","*","*"], ["-","-","-","-"]]

4) board: [["#","#","#","-"], ["*","-","#","#"], ["#","#","-","-"], ["#","-","#","#"], ["#","-","-","-"], ["-","-","-","-"], ["#","#","#","-"]] Expected return value

[["-","-","-","-"], ["*","-","-","-"], ["-","-","-","-"], ["#","-","#","-"], ["#","-","#","-"], ["#","#","#","#"], ["#","#","#","#"]]

5) board: [["-","-","#","-","#","*","#","-"], ["*","#","-","*","-","-","#","#"], ["-","*","*","#","#","#","#","-"]] Expected return value

[["-","-","-","-","-","*","#","-"], ["*","-","-","*","#","-","#","-"], ["-","*","*","#","#","#","#","#"]]

6) board: [["#","*","-","#","#","#","#","-","#","-"], ["*","-","-","#","-","#","#","#","-","#"], ["#","#","#","-","-","-","#","*","-","-"], ["-","#","-","-","-","*","-","-","#","#"], ["-","*","#","#","*","#","#","#","-","*"], ["#","*","#","#","*","#","*","-","-","#"], ["-","#","#","#","#","#","*","#","#","#"], ["-","#","#","#","-","#","#","#","#","#"], ["#","#","-","-","#","#","#","#","-","-"], ["#","-","-","-","#","#","-","#","-","#"]] Expected return value

[["-","*","-","-","-","-","-","-","-","-"], ["*","-","-","-","-","-","-","-","-","-"], ["-","-","-","-","-","-","-","*","-","-"], ["-","-","-","-","-","*","-","-","-","-"], ["-","*","-","#","*","-","-","-","-","*"], ["-","*","-","#","*","-","*","-","-","-"], ["-","-","-","#","-","-","*","-","-","#"], ["#","#","#","#","#","#","-","#","-","#"], ["#","#","#","#","#","#","#","#","#","#"], ["#","#","#","#","#","#","#","#","#","#"]]

Anyone please help me out in this problem