Как найти квадрат в двумерном массиве?

241

11 июня 2019, 16:40

Нашел задачу на двумерный массив и не понятно как код писать, сам недавно начал учит с++

Есть файл квадрат.txt

В первой строке находиться количество строк и столбцов, а дальше элементы двумерного массивa

Нужно найти самый большой квадрат

В теории выглядит так вроде: Чтение элементов с txt файла и дальше пойск

Начинается обход массива с левого верхнего элемента и проверяйется построчно , двигаясь слева на право.
Дальше проверяются элементы с координатами (X, Y),(X+1, Y+1), (X, Y+1), (X+1, Y). Если все они равны единице, то квадрат найден. В противном случае, массив не содержит квадрата.

Каким образом это можно реализовать в коде или не правильно?

Answer 1

Задача нахождения максимального квадрата - элементарна. Просто строим вторую матрицу по правилу

A[i][j] = min(A[i - 1][j], A[i - 1][j - 1], A[i][j - 1]) + 1

Первая строка и первый столбец - копия исходной матрицы. Остальные элементы вычисляются по вышеприведенному правилу.

Максимальный элемент A обозначит правый нижний угол (и размер) максимального квадрата.

Создание интернет-магазина строительных материалов в ABCname

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Реализация ассемблерной вставки [закрыт]

Найти сумму положительных элементов массива A = {a [i]}, что удовлетворяют условию: b <= a [i] <= dНаписал код но не могу понять почему оно не работает...

159

c++