To solve the problem of navigating a robot through a 2D grid while allowing for the demolition of a limited number of walls, we can use a breadth-first search (BFS) approach. This method will help us explore all possible paths the robot can take, considering the walls it can demolish.
Here's a JavaScript implementation of the function:
function canReachDestination(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
// BFS queue: [row, col, walls demolished]
const queue = [[0, 0, 0]];
const visited = new Set();
visited.add('0,0,0'); // Add the starting point with 0 walls demolished
while (queue.length > 0) {
const [x, y, wallsDemolished] = queue.shift();
// If we reach the bottom-right corner
if (x === rows - 1 && y === cols - 1) {
return true;
}
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
// Check if the new position is within bounds
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
const newWallsDemolished = wallsDemolished + grid[newX][newY];
// If we can demolish the wall and haven't visited this state yet
if (newWallsDemolished <= k && !visited.has(`${newX},${newY},${newWallsDemolished}`)) {
visited.add(`${newX},${newY},${newWallsDemolished}`);
queue.push([newX, newY, newWallsDemolished]);
}
}
}
}
return false; // If we exhaust the queue without reaching the destination
}
// Example usage:
console.log(canReachDestination([[0, 1, 0], [0, 1, 0]], 0)); // Output: false
console.log(canReachDestination([[0, 1, 0], [0, 1, 0]], 1)); // Output: true
console.log(canReachDestination([[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]], 0)); // Output: true
Explanation:
-
Initialization: We define the grid dimensions and possible movement directions (up, down, left, right). We also initialize a queue for BFS and a set to track visited states.
-
BFS Loop: We process each position in the queue:
- If we reach the bottom-right corner, we return
true.
- For each possible direction, we calculate the new position and check if it's within bounds.
- We calculate how many walls would be demolished if we move to the new position.
- If the number of walls demolished is within the allowed limit (
k) and we haven't visited this state before, we add it to the queue and mark it as visited.
-
Termination: If we exhaust the queue without reaching the destination, we return false.
This approach efficiently explores all possible paths while keeping track of the walls that can be demolished, ensuring that we find a valid path if one exists.