Другие языки программирования и технологии
Матрица M*N, состоящая из "0" и "1", найти наибольшую фигуру из единиц с помощью рекурсии. С++
Дана матрица M*N, состоящая из "0" и "1". Найти в ней наибольшую по площади фигуру, состоящую из единиц. Надо решить с помощью рекурсии. Помогите решить пожалуйсто.
int Arr[ M ][ N ];//заполняй сама
int FindFigureSize(int x,int y,int chr, int fill)//координаты, символ фигуры (единица) , символ заполнения, чтобы не повторяться
{
int s = 1;
Arr[ x ][ y ]=fill;
if ( ( x < M ) && (Arr [ x+1 ][ y ] == chr) )s+=FindFigureSize(x+1, y, chr, fill);
if ( ( y < N ) && (Arr [ x ][ y+1 ] == chr) )s+=FindFigureSize(x, y+1, chr, fill);
if ( ( x > 0 ) && (Arr [ x-1 ][ y ] == chr) )s+=FindFigureSize(x-1, y, chr, fill);
if ( ( y > 0 ) && (Arr [ x ][ y-1 ] == chr) )s+=FindFigureSize(x, y-1, chr, fill);
return s;
}
в main:
//вводишь массив, а потом
int fill=1,maxsize=0,maxfill=1;
for(int row = 0; row < M; row++)
for(int col = 0; col < N; col++)
{
int cursize;
if(Arr[ row ][ col ] == 1)cursize=FindFigureSize(row, col, 1, ++fill);//если где-то 1, считаем площадь
if(cursize > maxsize){maxsize=cursize;maxfill=fill;}//если площадь больше, сохраняем
}
Все, теперь выводим maxsize и при желании массив с указанием, что наибольшая фигура отмечена знаком maxfill
int FindFigureSize(int x,int y,int chr, int fill)//координаты, символ фигуры (единица) , символ заполнения, чтобы не повторяться
{
int s = 1;
Arr[ x ][ y ]=fill;
if ( ( x < M ) && (Arr [ x+1 ][ y ] == chr) )s+=FindFigureSize(x+1, y, chr, fill);
if ( ( y < N ) && (Arr [ x ][ y+1 ] == chr) )s+=FindFigureSize(x, y+1, chr, fill);
if ( ( x > 0 ) && (Arr [ x-1 ][ y ] == chr) )s+=FindFigureSize(x-1, y, chr, fill);
if ( ( y > 0 ) && (Arr [ x ][ y-1 ] == chr) )s+=FindFigureSize(x, y-1, chr, fill);
return s;
}
в main:
//вводишь массив, а потом
int fill=1,maxsize=0,maxfill=1;
for(int row = 0; row < M; row++)
for(int col = 0; col < N; col++)
{
int cursize;
if(Arr[ row ][ col ] == 1)cursize=FindFigureSize(row, col, 1, ++fill);//если где-то 1, считаем площадь
if(cursize > maxsize){maxsize=cursize;maxfill=fill;}//если площадь больше, сохраняем
}
Все, теперь выводим maxsize и при желании массив с указанием, что наибольшая фигура отмечена знаком maxfill
находишь первую единицу. помечаешь, как проверенную. находишь всех ее единиц-соседей. помечаешь их как проверенные. их сумма - очевидно, площадь.
после ищешь следующую непроверенную единицу - и т. д.
после ищешь следующую непроверенную единицу - и т. д.
Похожие вопросы
- Помогите испрвить код Переписать первые элементы каждой строки матрицы a(n*m), больше некоторого числа C, в массив b .
- Дана матрица размером n x m. Найти наибольший положительный и наименьший отрицательный элементы матрицы.
- В матрице А (m, n) (m<=5, n<=7)найти произведение элементов столбика, в котором находится максимальный элемент.
- Дано n строк по 3 элемента (1 и 0), найти сколько строк имеет больше чем один знак 1. C++
- как решить? Найти сумму элементов прямоугольной матрицы X(n,m), находящихся по периметру этой матрицы. язык: С++
- Дана действительная матрица размера n * m организовать однонаправленный список матрицы. Паскаль
- Вводится последовательность чисел, 0 – конец последовательности. Найти два наибольших числа (VB) прошу помощи
- Дано натуральное число n и вещественная матрица размера n X 9 . Плиз помогите(
- дана матрица размерности n*m . отсортировать ее строки по возрастанию. Сделать надо в basic
- ХЕЛП Дана квадратная матрица порядка n. на языке C или C ++