🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium
Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.
Пример:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
👨💻 Алгоритм:
1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов.
2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.
😎 Решение:
func countSquares(matrix [][]int) int {
m := len(matrix)
n := len(matrix[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == 1 {
if i == 0 || j == 0 {
dp[i][j] = 1
} else {
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
}
count += dp[i][j]
}
}
}
return count
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Ставь 👍 и забирай 📚 Базу знаний
