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
↵
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) = [['-', '-', '-', '-', '*'],↵
['-', '-', '-', '-', '-'],↵
['-', '-', '-', '-', '-'],↵
['-', '-', '-', '-', '-'],↵
['-', '*', '-', '-', '#'],↵
['#', '-', '*', '-', '#']]↵
↵
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) = [['-', '-', '*'],↵
['-', '-', '*'],↵
['-', '-', '*'],↵
['-', '-', '-'],↵
['*', '-', '-'],↵
['*', '-', '#'],↵
['*', '-', '#']]↵
↵
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
