Portfolio

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:


Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation:
There are10 squares of side 1.
There are4 squares of side 2.
There is1 square of side 3.
Total number of squares = 10 + 4 + 1 =15.

Example 2:


Input: matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation:
There are6 squares of side 1.
There is1 square of side 2.
Total number of squares = 6 + 1 =7.

Constraints:

1 <= arr.length <= 300

1 <= arr[0].length <= 300

0 <= arr[i][j] <= 1

풀이

효성


var countSquares = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const min = Math.min(m, n);
    let answer = 0;
    
    const isSubmatrices = (cnt, x, y) => {
        for(let j = 1; j <= cnt; j++) {
            const crossX = x + j;
            const crossY = y + j;
            
            if(crossX >= m || crossY >= n || !matrix[crossX][crossY]) {
                return false;
            }
            
            for(let i = 1; i <= j; i++) {
                if(crossX < i || crossY < i) {
                    return false;
                }
                const up = matrix[crossX - i][crossY];
                const left = matrix[crossX][crossY - i];
                
                if(!up || !left) {
                    return false;
                }
            }
        }
        return true;
    }
    
    for(let k = 0; k < min; k++) {
        for(let i = 0; i < m; i++) {
            for(let j = 0; j < n; j++) {
                if(matrix[i][j] && k === 0) {
                    answer += 1;
                }
                else if(matrix[i][j] && k > 0) {
                    if(isSubmatrices(k, i, j)) {
                        answer += 1;
                    }
                }
            }
        }
    }
    
    return answer;
};

똑똑한 풀이법이라 가져와써요,,


const countSquares = matrix => {
  let count = 0;
  for (let i = 0; i < matrix.length; ++i) {
    for (let j = 0; j < matrix[0].length; ++j) {
      if (matrix[i][j] === 0) continue;
      if (i > 0 && j > 0) {
        matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]);
      }
      count += matrix[i][j];
    }
  }
  return count;
};

재영


const countSquares = (matrix) => {
  const check = (row, col, len, rowLength, colLength) => {
    for (let i = row; i < row + len; i += 1) {
      if (i >= rowLength) return false;

      for (let j = col; j < col + len; j += 1) {
        if (j >= colLength) return false;
        if (!matrix[i][j]) return false;
      }
    }

    return true;
  };

  let count = 0;

  for (
    let len = 1;
    len <= Math.min(matrix.length, matrix[0].length);
    len += 1
  ) {
    for (let i = 0; i < matrix.length; i += 1) {
      for (let j = 0; j < matrix[0].length; j += 1) {
        if (check(i, j, len, matrix.length, matrix[0].length)) count += 1;
      }
    }
  }

  return count;
};

Count Square Submatrices with All Ones

풀이