We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Ema's Supercomputer
  5. Discussions

Ema's Supercomputer

  • tuan_lq121100
     + 0 comments

    After all, the best method is brute force. The idea is simple, you only need to travese the grid to find possible plus and then loop through these valid pluses to get the max product. Here is my js for the function. It might not be optimized, so feel free to upgrade it further.

    function isCellValid(grid, i, j) {
    if(!grid[i] || !grid[i][j]) return false;
    if(grid[i][j] === 'G') return true;
    else return false;
}
function isPlusOverlap(plus1, plus2) {
    const {i : i1, j : j1, count : count1} = plus1;
    const {i : i2, j : j2, count : count2} = plus2;
    let plusArr1 = [];
    let plusArr2 = [];
    for(let i=i1-count1+1;i<=i1+count1-1;i++){
        plusArr1.push({i, j:j1});
    }
    for(let j=j1-count1+1;j<=j1+count1;j++){
        plusArr1.push({i:i1, j});
    }
    for(let i=i2-count2+1;i<=i2+count2-1;i++){
        plusArr2.push({i, j:j2});
    }
    for(let j=j2-count2+1;j<=j2+count2-1;j++){
        plusArr2.push({i:i2, j});
    }
    const intersection = plusArr1.reduce((acc, value) => {
        let filteredArr = plusArr2.filter(obj => obj.i === value.i && obj.j === value.j)
        if (filteredArr.length > 0) {
            acc.push([...filteredArr]);
        }
        return acc;
    }, []);
    if(intersection.length > 0) return true;
    return false;
}

function twoPluses(grid) {
    // Write your code here
    let h = grid.length;
    let w = grid[0].length;
    let plusses = [];
    let output = 0;
    for(let i=1;i<h-1;i++){
        for(let j=1;j<w-1;j++){
            if(isCellValid(grid, i, j)){
                let count = 0;
                while(
                    isCellValid(grid, i-count,j) 
                    && isCellValid(grid, i+count, j)
                    && isCellValid(grid, i, j-count) 
                    && isCellValid(grid, i, j+count)
                    ){
                        count++;
                        plusses.push({
                            i, j, count
                        })
                    }

            }
        }
    }
    for(let k=0; k<plusses.length-1;k++) {
        let plus = plusses[k];
        let product = 0;
        for(let h=k+1; h<plusses.length; h++){
            let plus2 = plusses[h];
            if(!isPlusOverlap(plus, plus2)) {
                let tempProduct = (1+ 4*(plus.count-1)) * (1+ 4*(plus2.count-1));
                if(product < tempProduct) {
                    product = tempProduct;
                    console.log(plus, plus2, product);
                }
            }
        }
        if(output < product) output = product;
    }
    return output;
}