Как найти квадрат мак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,... и так пока не дойдёшь до конца матрицы).
- После этого нужно пройти по всем граням квадрата проверяя везде ли единицы.
- Если да то находишь площадь и записываешь. Если что-то не понятно - спрашивай.