В квадратной матрице, где каждая ячейка черная или белая. Разработайте алгоритм, чтобы найти максимальный подобласть таким образом, чтобы все 4 границы были черными

Question

Дана квадратная матрица, где каждая ячейка черная или белая. Разработайте алгоритм, чтобы найти максимальный подобласть таким образом, чтобы все 4 границы были черными.

У меня есть алгоритм O (n ^ 2):

Сканирование каждого столбца слева направо, для каждой ячейки каждого столбца, сканирование каждого ряда, чтобы найти максимальный квадрат с задними границами.

Есть ли лучшие решения?

спасибо

Answer 1

O (n ^ 2) возможно.Я думаю, это оптимально, так как у вас есть n ^ 2 ячеек.

Обратите внимание, что верхний левый угол и нижний правый угол любого квадрата лежат вдоль одной диагонали.

Теперь, еслимы могли бы обработать каждую диагональ за O (n) время, у нас был бы O (n ^ 2) алгоритм времени.

Скажем, у нас есть кандидат на верхний левый угол.Мы можем вычислить количество непрерывных черных ячеек под ним, а справа от него взять минимум двух и назвать его T.

Для нижнего правого кандидата мы можем вычислить количество непрерывных черных ячеек.черные клетки слева от него, а сверху и взять минимум из двух, назовите его B.

Как только у нас есть два числа T и B, мы можем сказать, если данный верхний левый,кандидат в правом нижнем углу фактически дает нам квадрат со всеми черными границами.

Теперь эти два числа можно вычислить для каждой ячейки за O (n ^ 2) времени, сделав четыре прохода через всю матрицу (Как?).

Итак, давайте предположим, что это сделано.

Теперь рассмотрим диагональ.Наша цель - найти верхнюю левую, нижнюю правую пару вдоль этой диагонали за O (n) времени.

Предположим, что мы вычислили T в массиве T [1 ... m], где m - длина диагонали.Точно так же у нас есть массив B [1 ... m].T [1] соответствует верхнему левому концу диагонали, а T [m] нижнему правому.Аналогично с B.

Теперь мы обрабатываем диагональ следующим образом: для каждого верхнего левого кандидата i мы пытаемся найти правого нижнего кандидата j, который даст наибольший квадрат.Обратите внимание, что j> = i.Также обратите внимание, что если (i, j) является кандидатом, то (i ', j) нет, где i'> i.

Обратите внимание, что i и j образуют квадрат, если T[i] >= j-i+1 и B[j] >= j-i+1.

т.е. T[i] +i - 1 >= j и B[j] -j - 1 >= -i.

Таким образом, мы формируем новые массивы, такие что TL[k] = T[k] + k -1 и BR[k] = B[k] -k - 1.

Итак, учитывая два новыхДля массивов TL и BR и a i нам нужно ответить на следующие запросы:

Какой самый большой j такой, что TL [i]> = j и BR [j]> = -i?

Теперь предположим, что мы смогли обработать BR для запросов с максимальным диапазоном (это можно сделать за время O (м)).

Теперь, учитывая TL [i], в диапазоне [i, TL [i]] мы находим максимальное значение BR, скажем, BR [j1].

Теперь, если BR [j1]> = -i, мы найдем максимум BR в диапазоне [j1,TL [i]] и продолжайте в том же духе.

Как только мы найдем кандидата (TL [i], BR [j]), мы можем игнорировать массив BR [1 ... j] для будущего i.

Это позволяет нам обрабатывать каждую диагональ за O (n) время, давая общий алгоритм O (n ^ 2).

Я упустил много деталей и дал набросокч, как это было уже слишком долго.Не стесняйтесь редактировать это с разъяснениями.

Фу.

Answer 2

Я не знаю, почему вы можете получить алгоритм O (n ^ 2).Математически это невозможно.Допустим, у вас есть матрица NxN.Вам необходимо проверить: 1. 1 матрицу размера: NxN, 2. 2 * 2 матрицы размера: (N-1) x (N-1), 3. 3 * 3 матрицы размера: (N-2) x(N-2), ....

В общей сложности вы должны проверить: 1+ 2 ^ 2 + 3 ^ 2 + ... + N ^ 2 = N (N + 1) (2N+ 1) / 6.Таким образом, любой алгоритм не может работать лучше, чем O (N ^ 3)

Answer 3

/* In a square matrix, where each cell is black or white. 
 * Design an algorithm to find the max sub-square such that all 4 borders are black. The right Java implementation based on a previous post. 
 */
public int maxSubsquare(boolean[][] M){
    int n = M.length; 
    maxsize=0; 
    checkDiag(M, 0, 0, n); 
    for (int i=1; i<n; i++){
        checkDiag(M, i, 0, n); 
        checkDiag(M, 0, i, n); 
    }
    return maxsize; 
}
int maxsize; 
void checkDiag(boolean[][] M, int i, int j, int n){
    if (i>=n-maxsize || j>=n-maxsize) return; 
    int step = 0; 
    while (step<(n-Math.max(i, j))&& M[i][j+step]&&M[i+step][j]){
        int s = step; 
        while (s>0){
            if (M[i+s][j+step]&&M[i+step][j+s]) s--; 
            else break; 
        }
        if (s==0) 
            maxsize = Math.max(maxsize, step+1); 
        step++; 
    }
    if (step==0) checkDiag(M, i+step+1, j+step+1, n); 
    else checkDiag(M, i+step, j+step, n); 
}

Answer 4

C ++ Код:

#include<iostream>
using namespace std;

int min(int a,int b,int c)
{
    int min = a;
    if(min > b)
        min = b;
    if(min > c)
        min = c;
    return min;
}

int main()
{
    const int size  = 5;
    char a[size][size] = { {'b','b','b','b','w'},{'b','b','b','b','b'},{'b','b','b','b','b'},{'b','b','w','b','b'},{'b','w','w','b','b'} };
    int arr[size+1][size+1];
    // First row and First column of arr is zero.
    for(int i=0;i<size+1;i++)
    {
        arr[0][i] = 0;
        arr[i][0] = 0;
    }
    int answer = 0;
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            if(a[i][j] == 'w')
                arr[i+1][j+1] = 0;
            if(a[i][j] == 'b')
            {
                int minimum = min(arr[i][i],arr[i+1][j],arr[i][j+1]);
                arr[i+1][j+1] = minimum + 1;
                if( arr[i+1][j+1] > answer)
                    answer = arr[i+1][j+1];
            }
        }
    }
    for(int i=0;i<size+1;i++)
    {
        for(int j=0;j<size+1;j++)
        {
            cout<<arr[i][j]<<"\t";
        }
        cout<<endl;
    }
    cout<<answer<<endl;
    return 0;
}