Robot Navigation with Wall Demolition in 2D Grid

Robot Navigation

A robot needs move from top left corner to bottom right corner in a 2D map. In this map, there are 0s and 1s. 0 means the robot can pass and 1 means the wall.

Please write a function that returns True or False, given at most k number of walls to demolish.

Note: The robots can only move up, down, left, right.

Example 1:

Input: grid = [[0, 1 0], [0, 1, 0]], k = 0 Output: False Explanation: The robot cannot demolish any wall due to k == 0, the robot cannot reach the bottom right corner.

Example 2:

Input: grid = [[0, 1 0], [0, 1, 0]], k = 1 Output: True Explanation: The robot can demolish the wall (0, 1) or (1, 1) to reach the destination.

Example 3:

input: grid = [[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]], k = 0 Output: True Explanation: The robot can first go down and then go up and then go down to reach the destination. The function interface should be: 请给出js实现代码

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:

1. 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.

2. 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.

3. 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.