Прямоугольники

← →
Николай Быков (2002-11-13 16:58) [0]

Условие:
На квадратном клечатом листе бумаги размером 100х100 клеток нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются.
Написать программу, которая считает число этих прямоугольников.

Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит массив 100х100, в котором элемент A[i,j]=1, если клетка [i,j] принадлежит какому-либо прямоугольнику, и A[i,j]=0, в противном случае.

Формат выходных данных:
В файл OUTPUT.TXT необходимо вывести единственное число - количество прямоугольников.

← →
RV (2002-11-13 17:15) [1]

Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.

??????

← →
RV (2002-11-13 17:17) [2]

а вообще-то легко, но

Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.

не понятно

← →
Johnny Smith (2002-11-13 17:19) [3]

Очередная задачка с олимпиады?

← →
RV (2002-11-13 17:23) [4]

причем похоже не меняются :)

у нас, правда, интереснее было :), но тоже прямоугольники,
и пересекаются/не пересекаются
и поле ограничено известно каким числом/ограничено неизвестно каким числом

← →
Феу (2002-11-13 17:24) [5]

Кажется, такое должно считаться намного быстрее 1с на нормальной машине (быстрее 8008 ;-)
Смотрим все по очереди, наткнувшись на прямоугольник считаем его, как-нибудь метим(можно просто стереть), чтоб не мешался, и ищем дальше.
Гм... с такими вопросами к людям... Может таки не здря тебя так тут пинают?
Или я всеж не понял про время и в нем вся заморолчка? Можт 0,00...1?

← →
Romkin (2002-11-13 17:29) [6]

Что-то вроде этого тебе катит? Вроде должно работать, правда, писал код прямо в форуме :-))

var InRect: boolean; RectCount:array [1..100] of integer; i,j: integer; AllRect: integer; begin for i := 1 to 100 do RectCount[i] := 0; InRect := false; for i := 1 to 100 do for j := 1 to 100 do begin if (A[i,j] = 1) and (not inRect) then begin inc(RectCount[i]); end; inRect := (A[i,j] = 1); end; AllRect := RectCount[1]; for i := 2 to 100 do if RectCount[i-1] < RectCount[i] then inc(AllRect, RectCount[i] - RectCount[i-1]); Result := AllRect; end;

← →
McSimm (2002-11-13 17:32) [7]

>Romkin © (13.11.02 17:29)
Что-то сомневаюсь...
Хотя может я и недопонял.

← →
Romkin (2002-11-13 17:36) [8]

О! массив можно и не пользовать :-)), считать в первом цикле, впрочем, это на любителя :-))

← →
Romkin (2002-11-13 17:37) [9]

2McSimm: Двойной цикл считает для каждой строки кол-во перемен с 0 на 1 - вход в прямоугольник (левая граница)
второй цикл по RectCount подсчитывает число верхних границ

← →
Дремучий (2002-11-13 17:52) [10]

если б соприкасались - было бы интересней...
:)

П.С. елки, уже по инерции хочется съязвить...

← →
DAC (2002-11-14 11:35) [11]

> Romkin © (13.11.02 17:29)

Красиво, но неверно! :)
Второй цикл лишён логического смысла.

Контрпример на матрице 3 на 3 :

var A : array [1..3,1..3] of integer; InRect: boolean; RectCount:array [1..3] of integer; i,j: integer; AllRect: integer; begin A[1,1] := 0; A[1,2] := 0; A[1,3] := 1; A[2,1] := 0; A[2,2] := 0; A[2,3] := 1; A[3,1] := 1; A[3,2] := 0; A[3,3] := 0; for i := 1 to 3 do RectCount[i] := 0; InRect := false; for i := 1 to 3 do for j := 1 to 3 do begin if (A[i,j] = 1) and (not inRect) then begin inc(RectCount[i]); end; inRect := (A[i,j] = 1); end; AllRect := RectCount[1]; for i := 2 to 3 do if RectCount[i-1] < RectCount[i] then inc(AllRect, RectCount[i] - RectCount[i-1]); Result := AllRect; end;

Здесь целых 3 прямоугольника, а Ваш алгоритм выдаст только 1.

Теперь Николашка (если он знает алгоритм) имеет полное моральное право утереть Вам нос! :)

← →
Romkin (2002-11-14 11:41) [12]

Там неточность: перед for j надо вставить inRect := false, просто не сбрасывает флаг

← →
Romkin (2002-11-14 11:43) [13]

А прямоугольника всего 2 :-))

← →
McSimm (2002-11-14 11:46) [14]

>Красиво, но неверно! :)
>Второй цикл лишён логического смысла.
Насчет логического смысла немного сильно сказано.
Небольшая огреха - InRect := false; надо не перед внешним, а перед внутренним циклом. И все.

← →
Ru (2002-11-14 11:48) [15]

вообще это задача прослеживания контуров
решается следующим образом: пробегаем по исходному массиву, находим первую ещиницу, заносим ее в массив точек контура, бегаем по маске в поисках следующей точки, когда дорвались до начальной точки контура - инкрементируем количество контуров, для исключения повторений мочим контур.

← →
DAC (2002-11-14 11:59) [16]

> Romkin © (14.11.02 11:43)

A[1,1] := 1; A[1,2] := 0; A[1,3] := 0; A[2,1] := 0; A[2,2] := 0; A[2,3] := 1; A[3,1] := 1; A[3,2] := 0; A[3,3] := 0;
Теперь 3. :)

> Romkin © (14.11.02 11:41)
McSimm © (14.11.02 11:46)

Не поможет.
Количество левых границ и верхних границ на соседних вертикалях могут совпадать, но это не означает одни и те же прямоугольники.

Успехов в решении школьной задачи! :-)))

← →
McSimm (2002-11-14 12:22) [17]

>Ru © (14.11.02 11:48)
>вообще это задача прослеживания контуров
есть вариант проще, подсчитать все (например) левые верхние углы

> DAC © (14.11.02 11:59)

Да уж, припер :)

Прямоугольники Найти похожие ветки