Как найти квадрат макcимальной площади?

Есть массив, условно 10Х10, он состоит из 0 и 1, надо найти квадрат максимальной площади, 1 должны выступать в роли его границ/сторон, что внутри квадрата не важно.

#include <iostream>

using namespace std;

int f(int** a, int k, int m) {
    int x, y, p, max;
    max = 0;
    for (int i = 0; i < m; i++) {
        x = 0;
        for (int j = i + 1; j < m; j++) {
            if (a[k][i] <= a[k][j])
                x++;
            else
                break;
        }
        y = 0;
        for (int j = i; j >= 0; j--) {
            if (a[k][i] <= a[k][j])
                y++;
            else
                break;
        }
        p = a[k][i] * (x + y);
        if (p > max)
            max = p;
    }
    return max;
}

int main() {
    int n, m, max, x, y;
    cout << "Enter a matrix size:\n";
    cout << "n = ";
    cin >> n;
    cout << "m = ";
    cin >> m;
    int** a = new int* [n];
    for (int i = 0; i < n; i++) {
        a[i] = new int[m];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = rand() % 2;
        }
    }
    for (int j = 0; j < m; j++) {
        for (int i = 1; i < n; i++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
    max = 0;
    for (int i = 0; i < n; i++) {
        if (f(a, i, m) > max)
            max = f(a, i, m);
    }

    cout << "Max square = " << max << "\n";
    
    for (int i = 0; i < n; i++) {
        delete[] a[i];
    }
    delete[] a;
    system("pause");
    return 0;
}

Ответы (1 шт):

Автор решения: Tiny

Расскажу один способ решения:

  1. Перебираешь все возможные координаты левого верхнего угла(просто проходишь массив).
  2. Перебираешь правый нижний угол(добавляешь к координатам левого верхнего 1,2,... и так пока не дойдёшь до конца матрицы).
  3. После этого нужно пройти по всем граням квадрата проверяя везде ли единицы.
  4. Если да то находишь площадь и записываешь. Если что-то не понятно - спрашивай.
→ Ссылка