Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > Помогите решить задачу с матрицей


Автор: Guest 4.6.2005, 08:59
Народ помогите решить задачу!
ДАна матрица n*N. Элементом этой матрицы может быть 1 или 0.
Если 0 - пустое место, 1- не пустое. Нужно найти кол-во прямоугольников, образованных
единичками. Прямоугольники не накладываются друг на друга и не соприкасаются.
Заранее спасибо!

Автор: gepard 5.6.2005, 06:08
Цитата(Guest @ 4.6.2005, 08:59)
ДАна матрица n*N.

Квадратная? Тогда уж n*m, если не квадратная...
В чём проблема решения задачи? Алгоритм? Реализация?

Вообще, это в раздел "Центр помощи" ИМХО

Автор: ChofCh 5.6.2005, 11:03
Количество прямоугольников равно количеству их верхних левых углов. Т.к. прямоугольники не пересекаются и не прикасаются друг к другу, то слева и сверху от л.в. угла прямоугольника должны быть нули (или границы массива). Код, котрым это можно реализовать, следущий:
Код

Const n=10
Const m=12
Private Sub main()
Dim A(0 to n-1, 0 to m-1) As Byte
Dim i as long, j as long
Dim fi as boolean, fj as boolean
Dim s as long
---------------------'здесь должен быть код, в котором матрицу заполняют
s=0
For i=0 to n-1
For j=0 to m-1
If A(i,j)=1 then
 fi=(i=0)
 If not(fi) then fi=(A(i-1,j)=0)
 fj=(j=0)
 If not(fj) then fj=(A(i,j-1)=0)
 If fi and fj then s=s+1
end if
Next j
Next i
MsgBox s
End sub

Автор: Guest 5.6.2005, 22:19
мне на c/c++ нада

Автор: ChofCh 5.6.2005, 23:27
Эх... C++ я практически не знаю, но этот код даже я смогу перевести:
Код

s=0;
For (i=0;i<n;i++)
{
 For (j=0;j<m;j++)
 {
  If (A[i][j])!=0)
  {
   If (i==0) f=1;
   else if (A[i-1][j]==0) f=1; else f=0;
   If (j==0) f++;
   else if (A[i][j-1]==0) f++;
   If (f==2) then s++;
  }
 }
}

Объявления опущены ввиду неполноты ТЗ (неивестно, что и откуда вводится/выводится и какие на это накладываются ограничения)

Автор: cardinal 6.6.2005, 01:25
Цитата(Guest @ 5.6.2005, 20:19)
мне на c/c++ нада

А сразу сказать? smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)