Другие языки программирования и технологии

Матрица 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
Андрей Andrei
Андрей Andrei
68 752
Лучший ответ
находишь первую единицу. помечаешь, как проверенную. находишь всех ее единиц-соседей. помечаешь их как проверенные. их сумма - очевидно, площадь.
после ищешь следующую непроверенную единицу - и т. д.

Похожие вопросы