Поиск прямоугольников.

@yoink · Регистрация: 04.11.2009

Студворк — интернет-сервис помощи студентам

Есть такая задача: дан массив 100х100 состоящий из нулей и единиц. Из единиц построены прямоугольники, так, что они не могут совпадать и пересекаться (между прямоугольниками всегда нули). Надо написать программу, которая считает эти прямоугольники.
Основное задание я сделал, но вот у меня такие проблемы: массив нужно задавать произвольно, то есть чтобы он создавал эти прямоугольники в произвольных местах и с заданным условием, чтобы они не пересекались. Помогите, пожалуйста, такое реализовать на C.
Над самим алгоритмом думал и пришел к такому заключению: задаем произвольные координаты двух точек, проверяем, нет ли рядом единиц, если есть смещаемся от них, и по двум этим точкам строим прямоугольник. Но все равно не понимаю, как это реализовать.

@odip · 04.11.2009, 22:36

Найти прямоугольники.
Достаточно посчитать левые верхние углы. Сколько углов - столько и прямоугольников.

Построить прямоугольники.
N - число попыток.
Сначала поле 100 x 100 не заполняем, а просто получим координаты всех.

Строим случайную пару (X,Y) - координаты левого верхнего угла.
Потом строим случайную пару (W,H) - ширина и высота.
Проверяем что построенный прямоугольник не пересекается с другими уже построенными.
И не лежит рядом !
Если все нормально - записываем координаты.
Если не нормально - отбрасываем.

Повторяем процедуру N раз.

Потом по заданным координатам заполняем поле 100x100.

Потом запускаем алгоритм подсчета прямоугольников.

Тест труднее сделать, чем алгоритм подсчета

@yoink · 05.11.2009, 00:22 **[ТС]**

Я конечно понимаю, что код и метод индусские (зато все свое)

Но помогите найти ошибку. Пишет, что "zadacha3 вызвал ошибку при использовании стека в модуле zadaxha3.exe"

C
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
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <math.h>;
#include <stdio.h>;
#include <conio.h>;
#include <stdlib.h>;
void main ()
{int mas[100][100],i,j,t,k,b = 0,n,kol,proverka=0;
float tI,tJ,tW,tH;
randomize();
printf ("\n Vvedite koli4estvo", kol);
scanf ("%d",&kol);
for (i=0; i<=kol;i++)
   {tI = double(rand()%100);
    tJ = double(rand()%100);
    tH = double(rand()%100);
    tW = double(rand()%100);
    proverka = 0;
    for (j=(tI-1);j<(tI+tW+2);j++)
      {for (k=(tJ-1);t<(tJ+tH+2);t++)
    {if (mas[j][t] == 1)
         proverka = 1;}
       }
    if (proverka != 0)
     break;
    for (j=tI;j<(tI+tW);j++)
      {for (k=tJ;t<(tJ+tH);t++)
     mas[j][t] = 1;}
    }
   for (i=0;i<100;i++)
    {for (j=0; j<100; j++)
         {if (mas[i][j] == 1)
         {for (t=0;t<100;t++)
              {for (n = i;n<100; n++)
                if (mas[n][j+t] == 1)
                mas[n][j+t] = 0;
                if (mas[n][j+t] == 0)
                break;
              }
               if (mas[i][j+t+1] == 0)
               {b = b + 1;
                break;}
         }
         }
    }
    printf ("%d",b);
}

@easybudda · 05.11.2009, 00:46

Сообщение от yoink

printf ("\n Vvedite koli4estvo", kol);

переменную kol отсюда уберите
printf ("\n Vvedite koli4estvo ");
и будет Вам счастье

@yoink · 05.11.2009, 00:54 **[ТС]**

ой, точно

))
стыдно даже

но все равно ошибка в 35й строчке.

@yoink · 08.11.2009, 16:35 **[ТС]**

В общем) Сегодня решил добить эту задачу. Решил сделать так: пусть вообще произвольное количество прямоугольников будет. И для того, чтобы нагляднее решить задачу, пускай будет массив 10 на 10 и будет выводиться, чтобы легче посчитать было. Вопрос: ошибка явно в алгоритме. Помогите пожалуйста.

C
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <math.h>;
#include <stdio.h>;
#include <conio.h>;
#include <stdlib.h>;
void main ()
{int mas[11][11],i,j,t,k,b = 0,n,kol,l;
randomize();
for (i=0;i<10;i++) {
 for (j=0;j<10;j++) {
  mas[i][j] = 1;
 }
}
for (i=10;i<=10;i++)
  for (j=0;j<11;j++)
   mas[i][j] = 0;
for (j=10;j<=10;j++)
  for (i=0;i<11;i++)
    mas[i][j] = 0;
kol = random(10);
i=0;
 do
    {l = random(10);
    for (j=l;j<=l;j++)
      for (n=0;n<10;n++)
    mas[j][n] = 0;
    for (n=l;n<=l;n++)
      for (j=0;j<10;j++)
    mas[j][n] = 0;
     i++;
    }
    while (i<=kol);
for (i=0;i<11;i++)
  {for (j=0;j<11;j++)
     {printf (" %d ",mas[i][j]);}
      printf ("\n");}
   for (i=0;i<10;i++)
    {for (j=0; j<10; j++)
         {if (mas[i][j] == 1)
         {for (t=0;t<10;t++)
              {for (n = i;n<10; n++)
                if (mas[n][j+t] == 1)
                mas[n][j+t] = 0;
                if (mas[n][j+t] == 0)
                break;
              }
               if (mas[i][j+t+1] == 0)
                           {b = b + 1;
                break;}
         }
         }
    }
    printf ("\n %d",b);
}

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@yoink 0 / 0 / 0 Регистрация: 04.11.2009 Сообщений: 4

	Поиск прямоугольников. 04.11.2009, 13:58. Показов 3742. Ответов 5 Метки нет (Все метки) Есть такая задача: дан массив 100х100 состоящий из нулей и единиц. Из единиц построены прямоугольники, так, что они не могут совпадать и пересекаться (между прямоугольниками всегда нули). Надо написать программу, которая считает эти прямоугольники. Основное задание я сделал, но вот у меня такие проблемы: массив нужно задавать произвольно, то есть чтобы он создавал эти прямоугольники в произвольных местах и с заданным условием, чтобы они не пересекались. Помогите, пожалуйста, такое реализовать на C. Над самим алгоритмом думал и пришел к такому заключению: задаем произвольные координаты двух точек, проверяем, нет ли рядом единиц, если есть смещаемся от них, и по двум этим точкам строим прямоугольник. Но все равно не понимаю, как это реализовать. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	04.11.2009, 22:36
	Найти прямоугольники. Достаточно посчитать левые верхние углы. Сколько углов - столько и прямоугольников. Построить прямоугольники. N - число попыток. Сначала поле 100 x 100 не заполняем, а просто получим координаты всех. Строим случайную пару (X,Y) - координаты левого верхнего угла. Потом строим случайную пару (W,H) - ширина и высота. Проверяем что построенный прямоугольник не пересекается с другими уже построенными. И не лежит рядом ! Если все нормально - записываем координаты. Если не нормально - отбрасываем. Повторяем процедуру N раз. Потом по заданным координатам заполняем поле 100x100. Потом запускаем алгоритм подсчета прямоугольников. Тест труднее сделать, чем алгоритм подсчета 1

@yoink 0 / 0 / 0 Регистрация: 04.11.2009 Сообщений: 4
	05.11.2009, 00:54 [ТС]
	ой, точно )) стыдно даже но все равно ошибка в 35й строчке. 0