Представьте, что существует квадратная матрица, каждый пиксел которой может быть черным или белым. Разработайте алгоритм поиска максимального субквадрата, у которого все стороны черные
Эту задачу также можно решить двумя способами: простым и сложным. Давайте рассмотрим оба решения.
«Простое» решение: O(N4)
Мы знаем, что длина стороны самого большого квадрата равна N и существует только один квадрат размером N*N. Можно проверить, является ли квадрат искомым, и сообщить, если это так.
Если квадрат размером N*N не найден, можно попытаться найти следующий квадрат: (N-1)*(N-1). Проверяя все квадраты этого размера, мы возвращаем первый найденный квадрат. Затем аналогичные операции повторяются для N-2, N-3 и т. д. Так как каждый раз мы уменьшаем размер квадрата, то первый найденный квадрат будет самым большим.
Наш код работает так:
Subsquare findSquare(int[][] matrix) {
for (int i = matrix.length; i >= 1; i--) {
Subsquare square = findSquareWithSize(matrix, i);
if (square != null) return square;
}
return null;
}
Subsquare findSquareWithSize(int[][] matrix, int squareSize) {
/* На стороне размером N есть (N - sz + 1) квадратов
* длины sz. */
int count = matrix.length - squareSize + 1;
/* Перебор всех квадратов со стороной squareSize. */
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(matrix, row, col, squareSize)) {
return new Subsquare(row, col, squareSize);
}
}
}
return null;
}
boolean isSquare(int[][] matrix, int row, int col, int size) {
// Проверяем верхнюю и нижнюю стороны
for (int j = 0; j < size; j++){
if (matrix[row][col+j] == 1) {
return false;
}
if (matrix[row+size-l][col+j] == 1){
return false;
}
}
// Проверяем левую и правую стороны
for (int 1=1; i < size - 1; i++){
if (matrix[row+i][col] == 1){
return false;
}
if (matrix[row+i][col+size-1] == 1){
return false;
}
}
return true;
}
Решение с предварительной обработкой: O(N3)
Неторопливость «простого» решения связана с тем, что мы должны произвести O(N) операций при каждой проверке квадрата–кандидата. Проведя предварительную обработку, можно сократить время isSquare до O(1), тогда алгоритм потребует O(N3) времени.
isSquare пытается узнать, не являются ли нулевыми squareSize, находящиеся правее (и ниже) определенных ячеек. А эту информацию можно узнать заранее.
Мы выполним проверку справа налево и снизу вверх. Для каждой ячейки нужно рассчитать:
если А[r][с] является белым, А[r][с].zerosRight = 0 и A[r][с].zerosBelow = 0
иначе A[r][c].zerosRight = А[r][с + 1].zerosRight + 1
А[r][с].zerosBelow = А[r + 1][с].zerosBelow + 1
Посмотрите на значения для некоторой матрицы.
Далее приведен код этого алгоритма. Обратите внимание, что findSquare и findSquare — WithSize совпадают, за исключением вызова processMatrix и последующей работы с новым типом данных:
public class SquareCell {
public int zerosRight = 0;
public int zerosBelow = 0;
/* объявления, функции установки и получения значений */
}
Subsquare findSquare(int[][] matrix) {
SquareCell[][] processed = processSquare(matrix);
for (int i = matrix.length; i >= 1; i--) {
Subsquare square = findSquareWithSize(processed, i);
if (square != null) return square;
}
return null;
}
Subsquare findSquareWithSize(SquareCell[][] processed,
int squareSize) {
/* эквивалентна первому алгоритму */
}
boolean isSquare(SquareCell[][] matrix, int row, int col,
int size) {
SquareCell topLeft = matrix[row][col];
SquareCell topRight = matrix[row][col + size - 1];
SquareCell bottomRight = matrix[row + size - l][col];
if (topLeft.zerosRight < size) { // Проверяем верхнюю сторону
return false;
}
if (topLeft.zerosBelow < size) { // Проверяем левую сторону
return false;
}
if (topRight.zerosBelow < size) { // Проверяем правую сторону
return false;
}
if (bottomRight.zerosRight < size) { // Проверяем нижнюю сторону
return false;
}
return true;
}
SquareCellf][] processSquare(int[][] matrix) {
SquareCell[][] processed =
new SquareCell[matrix.length][matrix.length];
for (int г = matrix.length - 1; г >= 0; r--) {
for (int c = matrix.length - 1; c >= 0; c--) {
int rightZeros = 0;
int belowZeros = 0;
// нужно обработать, только если ячейка черная
if (matrix[r][с] == 0) {
rightZeros++;
belowZeros++;
// следующая колонка в этом ряду
if (с + 1 < matrix.length) {
SquareCell previous = processed[r][с + 1];
rightZeros += previous.zerosRight;
}
if (r + 1 < matrix.length) {
SquareCell previous = processed[r + 1][c];
belowZeros += previous.zerosBelow;
}
}
processed[r][c] = new SquareCell(rightZeros, belowZeros);
}
}
return processed;
}
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»
