Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

здравствуйте не могли бы вы мне подсказать, как решать такую задачу

у нас есть массив NxN который заполнен нулями и единицами
(максимальное N=100)
нужно найти максимальное количество единиц, которые "соединены"

1 0 0 0 0
0 1 0 0 1
0 1 0 1 1
1 1 0 0 0
0 0 0 0 1

в данном случае ответ будет 4
как реализовать поиск максимального количества "соединенных" единиц?
заранее спасибо!

Вопрос задал: Ruslan (статус: 1-ый класс) Вопрос отправлен: 15 ноября 2009, 12:30 Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Паровоз

Здравствуйте, Ruslan!
Есть такой вариант:

const
  N=5;
type
  TArray=array[1..n,1..n] of Integer;
var
  MainArray:TArray;
 
procedure FillRegion(m,k:Integer;var ar:TArray);
begin
  ar[m,k]:=1;
  if (m>1)and(MainArray[m-1,k]=1) then
    begin MainArray[m-1,k]:=0;ar[m-1,k]:=1;FillRegion(m-1,k,ar);end;
  if (m<n)and(MainArray[m+1,k]=1) then
    begin MainArray[m+1,k]:=0;ar[m+1,k]:=1;FillRegion(m+1,k,ar);end;
  if (k>1)and(MainArray[m,k-1]=1) then
    begin MainArray[m,k-1]:=0;ar[m,k-1]:=1;FillRegion(m,k-1,ar);end;
  if (k<n)and(MainArray[m,k+1]=1) then
    begin MainArray[m,k+1]:=0;ar[m,k+1]:=1;FillRegion(m,k+1,ar);end;
end;
 
function RegionWeight(ar:TArray):Integer;
var
  i,j:Integer;
begin
  Result:=0;
  for i:=1 to n do for j:=1 to n do if ar[i,j]=1 then Inc(Result);
end;
 
function ElementWeight(m,k:Integer;ar:TArray):Integer;
var
  i,j:Integer;
begin
  if MainArray[m,k]=0 then Result:=0 else
  begin
    for i:=1 to n do for j:=1 to n do ar[i,j]:=0;
    FillRegion(m,k,ar);
    Result:=RegionWeight(ar);
  end;
end;
 
function MatrixWeight(ar:TArray):Integer;
var
  i,j:Integer;
  tmp:Integer;
begin
  Result:=0;
  for i:=1 to n do for j:=1 to n do
  begin
    tmp:=ElementWeight(i,j,ar);
    if Result<tmp then Result:=tmp;
  end;
end;
 
procedure ShowArray(ar:TArray;AMemo:TMemo);
var
  i,j:Integer;
  s:string;
begin
  AMemo.Clear;
  for i:=1 to n do
  begin
    s:='';
    for j:=1 to n do
    begin
      s:=s+IntToStr(ar[i,j])+'  ';
    end;
    AMemo.Lines.Add(s);
  end;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i,j:Integer;
begin
  Randomize;
  for i:=1 to n do for j:=1 to n do MainArray[i,j]:=Random(2);
  ShowArray(MainArray,Memo1);
  Memo1.Lines.Add('cnt='+IntToStr(MatrixWeight(MainArray)));
end;

Ответ отправил: Паровоз (статус: 10-ый класс) Время отправки: 15 ноября 2009, 18:36 Оценка за ответ: 5

Мини-форум вопроса

min@y™ (статус: Доктор наук), 15 ноября 2009, 12:34 [#1]: Соединены - это только последовательно по горизонтали или как-нибудь ещё, например, по вертикали, в куче и т.д.? Делаю лабы и курсачи по Delphi и Turbo Pascal. За ПИВО! Пишите в личку, а лучше в аську. А ещё лучше - звоните в скайп!

Ruslan (статус: 1-ый класс), 15 ноября 2009, 12:36 [#2]: соединены - по горизонтали и по вертикали а по диагонали - уже не соединены в примере 4 - это элементы a[2,2] a[3,2] a[4,2] a[4,1] a[1,1] с ними не "соединен"

Ruslan (статус: 1-ый класс), 15 ноября 2009, 12:54 [#3]: 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 Здесь ответ должен быть = 12 помогите пож.!

Егор (статус: 10-ый класс), 15 ноября 2009, 17:27 [#4]: хы идея такая - берём первый элемент, который "1", переименовываем его в "2" и все рядом стоящие переделываем в "2" и считаем, сколько же этих "2" будет (а можно и потом посчитать). потом ищем следующий элемент "1", переименовываем его в "3" и ищем все рядом стоящие "1", переименовывая их в "3", считаем при этом кол-во таких элементов. и т.д. потом можно будет даже показать. какая именно последовательность самая большая. реализовать сможешь? Опасайтесь багов в приведенном выше коде; я только доказал корректность, но не запускал его. — Donald E. Knuth.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.