С Новым годом! Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.65/34: Рейтинг темы: голосов - 34, средняя оценка - 4.65
7 / 7 / 0
Регистрация: 21.02.2010
Сообщений: 107

Поиск прямоугольников в матрице

22.02.2010, 12:51. Показов 6998. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите решить. На квадратном клетчатом листе бумаги нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются. В квадратной таблице А[1:N,1:N] элемент A[i,j]=1, если клетка [i,j] принадлежит какому -либо прямоугольнику, и A[i,j]=0 в противном случае. Вычислить количество прямоугольников.
Входной файл содержит в себе информацию о размере таблицы и элементы таблиц по строкам, в выходном файле количесвто прямоугольников.

дан пример входного и выходного файла:
входной:
8
1 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0
0 0 0 1 1 1 1 0
0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0
Выходной:
4

как считать информацию из файла я поняла (делаю так):

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
program name;
uses crt;
var f1,f2: Text; a:array[1..40,1..40] of integer; i,j,n:integer;
begin
     clrscr;
       assign(f1,'1.txt');
       assign(f2,'2.txt');
     reset(f1);
     read(f1,n);
       i:=1;j:=1;
     for i:=1 to n do begin
          for j:=1 to n do begin
               read(f1,a[i,j]);
          end;
     end;
 
     close(f1);
     readkey;
end.
А вот как теперь в свойе матрице подсчитать количество не понимаю, помогите, мне не столько важно решение, сколько объяснить как это просчитать.
1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.02.2010, 12:51
Ответы с готовыми решениями:

Сколько прямоугольников в матрице
На квадратном клетчатом листе бумаги(размера МхМ клеток) нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых...

Подсчитать количество прямоугольников из единиц в матрице
На снимке из космоса были обнаружены прямоугольные объекты. Необходимо подсчитать их количество. Снимок представляет из себя квадратную...

Поиск прямоугольников.
Есть такая задача: дан массив 100х100 состоящий из нулей и единиц. Из единиц построены прямоугольники, так, что они не могут совпадать и...

8
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
22.02.2010, 13:01
Лучше сделать массив с расчётом на то, что программ будет доходить до краёв (a:array[0..41,0..41])
Сам алгоритм программы:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
k:=0; {счётчик прямоугольников}
for i:=1 to n do {перебираем все клетки}
for j:=1 to n do
if a[i,j]=1 then {если встречаем закрашенную, то она будет верхним левым углом прямоугольника}
begin
 inc(k); {+1 прямоугольник}
 ii:=i; {в ii и jj будет хранить координаты правого нижнего угла}
 jj:=j;
 while a[i,jj]=1 do inc(jj); {ищем эти края по горизонтали}
 while a[j,ii]=1 do inc(ii); {и веритикали}
 for k:=i to ii do {стираем найденный прямоугольник, так как его уже мы проверили}
 for j:=j to jj do a[k,j]:=0;
end;
0
7 / 7 / 0
Регистрация: 21.02.2010
Сообщений: 107
22.02.2010, 13:18  [ТС]
В итоге у меня получился вот такой код:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
program name;
uses crt;
var f1,f2: Text; a:array[1..41,1..41] of integer; i,j,n,k,ii,jj:integer;
begin
clrscr;
assign(f1,'1.txt');
assign(f2,'2.txt');
reset(f1);
read(f1,n);
i:=1;j:=1;
for i:=1 to n do begin
for j:=1 to n do begin
read(f1,a[i,j]);
end;
end;
 k:=0;
for i:=1 to n do
for j:=1 to n do
[B]if a[i,j]=1 then[/B]
begin
 inc(k);
 ii:=i;
 jj:=j;
 while a[i,jj]=1 do inc(jj);
 while a[j,ii]=1 do inc(ii);
 for k:=i to ii do
 for j:=j to jj do a[k,j]:=0;
end;
close(f1);
writeln (k);
readkey;
end.
Программа выдает ошибку Range check error, указывает на строку №20.
1
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
22.02.2010, 13:23
Juliette58, скорее всего ошибки с чтением файла, его надо сделать следующим образом:
Pascal
1
2
3
4
5
6
7
reset(f1);
readln(f1,n);
for i:=1 to n do
begin
 for j:=1 to n do read(f1,a[i,j]);
 readln(f1);
end;
Добавлено через 2 минуты
И ещё: 28-я строка:
Pascal
1
for l:=j to jj do a[k,l]:=0;
0
7 / 7 / 0
Регистрация: 21.02.2010
Сообщений: 107
22.02.2010, 13:32  [ТС]
Сейчас ошибок не выдает, но считает не правильно, в ответе вывел 7. я не могу понять как он считает и как должен.
0
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
22.02.2010, 13:40
Juliette58, испрвил некоторые ошибки:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
uses crt;
var f1: Text; a:array[1..41,1..41] of integer;
i,j,n,k,c,ii,jj,l:integer;
begin
 clrscr;
 assign(f1,'1.txt');
 reset(f1);
 readln(f1,n);
 for i:=1 to n do
 begin
  for j:=1 to n do read(f1,a[i,j]);
  readln(f1);
 end;
 close(f1);
 
 c:=0;
 for i:=1 to n do
 for j:=1 to n do
 if a[i,j]=1 then
 begin
  inc(c);
  ii:=i;
  jj:=j;
  while a[i,jj]=1 do inc(jj);
  while a[ii,j]=1 do inc(ii);
  for k:=i to ii do
  for l:=j to jj do a[k,l]:=0;
 end;
 writeln(c);
end.
1
7 / 7 / 0
Регистрация: 21.02.2010
Сообщений: 107
22.02.2010, 13:45  [ТС]
Огромнейшее спасибо, но если не сложно объясните как все таки рабоотает, сам принцип. Это надо было просто старые обнулить чтоб больше их не трогать?
0
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
22.02.2010, 13:50
Цитата Сообщение от Juliette58 Посмотреть сообщение
Это надо было просто старые обнулить чтоб больше их не трогать?
Всё верно.

Не по теме:

С какой олимпиады задачка?:)

1
7 / 7 / 0
Регистрация: 21.02.2010
Сообщений: 107
22.02.2010, 13:57  [ТС]
с регионального заочного тура в городе Пенза и её областей среди ссузов 2008, просто в этом году меня отправили, а я даже смысла задач с того года понять не могу. Только позориться еду...((( (А эта задачка только под номером 2, дальше - хуже)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.02.2010, 13:57
Помогаю со студенческими работами здесь

Подсчет "черных прямоугольников" в матрице
Задача состоит в следующем: Подсчитать количество черных прямоугольников на клетчатом поле MxN. Если квадратик черный то значение...

Даны стороны трех прямоугольников Найти периметры и площади этих прямоугольников
1. S1=SSS(a1, b1); S2=SSS(a2, b2); S3=SSS(a3, b3); -------------------------------- int SSS(int a, int b) { return (a*b);...

Известны длины сторон двух прямоугольников. Вычислить площади прямоугольников и сравнить их. Определить, являются ли прямоугольники квадратами...
Привет , ребята нужна помощь Разместите на форме Элементы управления для решения задачи Известны длины сторон двух прямоугольников....

Объединение прямоугольников (количество объединенных прямоугольников минимально)
Добрый день. Прошу помощи в выполнении задачи. Дан список прямоугольников, которые задаются координатами верхней левой вершины и...

7. Пусть дано n прямоугольников, заданных координатами левой верхней и правой нижней вершины. Стороны прямоугольников параллельны осям координат. Опр
Пусть дано n прямоугольников, заданных координатами левой верхней и правой нижней вершины. Стороны прямоугольников параллельны осям...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru