Path in a Rectangle with Circles

// JavaScript program to find out path in
// a rectangle containing circles
// program to implement queue data structure

// Creating a custom class Queued. 
class Queued {
    constructor() {
        this.items = [];
    }
    
    // add element to the queue
    enqueue(element) {
        return this.items.push(element);
    }
    
    front(){
        return this.items[0];
    }
    
    // remove element from the queue
    dequeue() {
        if(this.items.length > 0) {
            return this.items.shift();
        }
    }
    
    // view the last element
    peek() {
        return this.items[this.items.length - 1];
    }
    
    // check if the queue is empty
    isEmpty(){
       return this.items.length == 0;
    }
   
    // the size of the queue
    size(){
        return this.items.length;
    }
 
    // empty the queue
    clear(){
        this.items = [];
    }
}

// Function to find out if there is
// any possible path or not.
function isPossible(m, n, k, r, X, Y)
{
    // Take an array of m*n size and
    // initialize each element to 0.
    let rect = new Array(m);
    for(let i = 0; i < m; i++){
        let temp = new Array(n).fill(0);
        rect[i] = temp;
    }

    // Now using Pythagorean theorem find if a
    // cell touches or within any circle or not.
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let p = 0; p < k; p++) {
                if (Math.sqrt((Math.pow((X[p] - 1 - i), 2) + Math.pow((Y[p] - 1 - j), 2))) <= r) {
                    rect[i][j] = -1;
                }
            }
        }
    }

    // If the starting cell comes within
    // any circle return false.
    if (rect[0][0] == -1){
        return false;
    }

    // Now use BFS to find if there
    // is any possible path or not.

    // Initialize the queue which holds
    // the discovered cells whose neighbors
    // are not discovered yet.
    let qu = new Queued();

    rect[0][0] = 1;
    qu.enqueue([0, 0]);

    // Discover cells until queue is not empty
    while (!qu.isEmpty()) {
        let arr = qu.front();
        qu.dequeue();
        let elex = arr[0];
        let eley = arr[1];

        // Discover the eight adjacent nodes.
        // check top-left cell
        if ((elex > 0) && (eley > 0) && (rect[elex - 1][eley - 1] == 0)) {
            rect[elex - 1][eley - 1] = 1;
            let v = [elex - 1, eley - 1];
            qu.enqueue(v);
        }

        // check top cell
        if ((elex > 0) && (rect[elex - 1][eley] == 0)) {
            rect[elex - 1][eley] = 1;
            let v = [elex - 1, eley];
            qu.enqueue(v);
        }

        // check top-right cell
        if ((elex > 0) && (eley < n - 1)
            && (rect[elex - 1][eley + 1] == 0)) {
            rect[elex - 1][eley + 1] = 1;
            let v = [elex - 1, eley + 1];
            qu.enqueue(v);
        }

        // check left cell
        if ((eley > 0) && (rect[elex][eley - 1] == 0)) {
            rect[elex][eley - 1] = 1;
            let v = [elex, eley - 1];
            qu.enqueue(v);
        }

        // check right cell
        if ((eley < n - 1) && (rect[elex][eley + 1] == 0)) {
            rect[elex][eley + 1] = 1;
            let v = [elex, eley + 1];
            qu.enqueue(v);
        }

        // check bottom-left cell
        if ((elex < m - 1) && (eley > 0) && (rect[elex + 1][eley - 1] == 0)) {
            rect[elex + 1][eley - 1] = 1;
            let v = [elex + 1, eley - 1];
            qu.enqueue(v);
        }

        // check bottom cell
        if ((elex < m - 1) && (rect[elex + 1][eley] == 0)) {
            rect[elex + 1][eley] = 1;
            let v = [elex + 1, eley];
            qu.enqueue(v);
        }

        // check bottom-right cell
        if ((elex < m - 1) && (eley < n - 1) && (rect[elex + 1][eley + 1] == 0)) {
            rect[elex + 1][eley + 1] = 1;
            let v = [elex + 1, eley + 1];
            qu.enqueue(v);
        }
    }

    // Now if the end cell (i.e. bottom right cell)
    // is 1(reachable) then we will send true.
    return (rect[m - 1][n - 1] == 1);
}

// Driver Program
{

    // Test case 1
    let m1 = 5, n1 = 5, k1 = 2, r1 = 1;
    let X1 = [1, 3];
    let Y1 = [3, 3];

    // Function call
    if (isPossible(m1, n1, k1, r1, X1, Y1)){
        console.log("Possible");
    }
    else{
        console.log("Not Possible");
    }

    // Test case 2
    let m2 = 5, n2 = 5, k2 = 2, r2 = 1;
    let X2 = [1, 1];
    let Y2 = [2, 3];

    // Function call
    if (isPossible(m2, n2, k2, r2, X2, Y2)){
        console.log("Possible");
    }
    else{
        console.log("Not Possible");
    }
}

// The code is contributed by Nidhi goel