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) = [['-', '-', '-', '-', '*'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '*', '-', '-', '#'], ['#', '-', '*', '-', '#']] For board = [['#', '#', '*'], ['#', '-', '*'], ['#', '-', '*'], ['-', '#', '#'], ['*', '-', '#'], ['*', '-', '-'], ['*', '-', '-']] the output should be solution(board) = [['-', '-', '*'], ['-', '-', '*'], ['-', '-', '*'], ['-', '-', '-'], ['*', '-', '-'], ['*', '-', '#'], ['*', '-', '#']]
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
Auto comment: topic has been updated by bharatim1221 (previous revision, new revision, compare).
Bonus problem: suppose that the boxes infinitely move down with given acceleration and zero start velocity and when the box hits the bottom it goes to the ceil and keeps falling without the loss of velocity. But when it hits an obstacle it loses its velocity (but not acceleration). Given k determine the state after k seconds. If two boxes share the same cell or the box share the same cell with an obstacle, just output one box.