FastPrep
Problem · Matrix

Minimum Obstacles To Remove To Allow Figure Fall

Learn this problem
● MediumMetaNEW GRADOA
See Meta hiring insights

Problem statement

Note - See the problem source section below for the original prompt 🐰🐰

10000 years agooooo, in the magical land of Gravity Falls, you found yourself playing a challenging puzzle game involving a mysterious, oddly-shaped figure that needed to fall gracefully to the bottom of a rectangular board. The board was made up of three types of enchanted cells: empty cells marked as '-', obstacles marked as '#', and the figure itself made of '*'. The figure was a single piece, with all of its parts connected by their sides, and it longed to touch the bottom of the board. Your quest was to help the figure descend by removing obstacles in its way, but only as many as absolutely necessary for it to finally touch the ground with at least one of its cells. The council of Gravity Falls understood that the task need not be approached in the most cunning way, but rather in a manner where you could explore every nook and cranny in at most board.length * board[0].length steps, solving the puzzle while uncovering the secrets of this gravity-bound world.

Function

minimumObstaclesToRemoveToAllowFigureFall(matrix: char[][]) → int

Examples

Example 1

matrix = [["*","*","*"],["#","*","*"],["*","*","-"],["-","*","-"],["-","#","#"]]return = 2

The figure needs to fall one row before one of its cells touches the bottom. During that movement it would collide with the obstacles at [1,0] and [4,1]. Removing those two obstacles is necessary and sufficient.

Constraints

🍎🍎

More Meta problems

drafts saved locally
public int minimumObstaclesToRemoveToAllowFigureFall(char[][] matrix) {
 // write your code here
}
matrix[["*","*","*"],["#","*","*"],["*","*","-"],["-","*","-"],["-","#","#"]]
expected2
checking account