Форум программистов, компьютерный форум CyberForum.ru

Сколько прямоугольников в матрице - C++

Восстановить пароль Регистрация
 
kitap
 Аватар для kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
13.03.2014, 14:38     Сколько прямоугольников в матрице #1
На квадратном клетчатом листе бумаги(размера МхМ клеток) нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются (см. пример).
Задан размер массива М. Затем построчно задается сам массив размером МхМ, в котором элемент A(i,j)=1, если клетка (i,j) принадлежит какому-либо прямоугольнику, и A(i,j)=0 в противном случае.
Сосчитать число прямоугольников в заданном массиве.


Пример
содержимое файла:
8
10000000
00011100
10011100
10011100
00000000
00001110
00001110
00000000
Ответ : 4 прямоугольника
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2014, 14:38     Сколько прямоугольников в матрице
Посмотрите здесь:

C++ Пересечение прямоугольников
C++ С++ Метод прямоугольников
У меня задача,в матрице,заменить первый отрицательный элемент максимальным элементом. Проходить по матрице слева направо,сверху вниз C++
C++ C++ матрица и вектор ( Для каждого элемента вектора определить, сколько раз он встречается в матрице)
В матрице К размером m*n найти в каждом столбце произведение отрицательных элементов и количество нулевых элементов в матрице C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
13.03.2014, 16:17     Сколько прямоугольников в матрице #2
kitap, если действовать не особо думая (а я так и действовал), то можно тупо пробежаться по матрице. Если встречается 1, то счетчик прямоугольников увеличивается на 1, а все рядом стоящие единицы переименовываются в 0. Итого у нас останется матрица из 0 и количество найденных "полей" из единичек
kitap
 Аватар для kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
14.03.2014, 07:18  [ТС]     Сколько прямоугольников в матрице #3
я так и хотел сделать но как мне сделать 0-ли рядом стояших единиц
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 07:43     Сколько прямоугольников в матрице #4
kitap, минут через 20 сяду к компу и скину вариант решения
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
14.03.2014, 07:54     Сколько прямоугольников в матрице #5
Цитата Сообщение от TenGen Посмотреть сообщение
kitap, если действовать не особо думая (а я так и действовал), то можно тупо пробежаться по матрице. Если встречается 1, то счетчик прямоугольников увеличивается на 1,
сколько прямоугольников в такой записи ?
0 0 0 0 0
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:09     Сколько прямоугольников в матрице #6
ValeryS, вы на самом деле думаете, что им по заданию требуют вот такие головоломки? Я считаю, что там вводятся только прямоугольные области
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
14.03.2014, 08:15     Сколько прямоугольников в матрице #7
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
#include <iostream>
 
int main ()
{
    const int M = 8;
    int count = 0;
    int A[M][M] = { {0, 0, 0, 1, 1, 0, 0, 0},
                    {1, 1, 0, 1, 1, 0, 0, 0},
                    {1, 1, 0, 1, 1, 0, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 1},
                    {0, 1, 1, 0, 1, 1, 0, 0},
                    {0, 1, 1, 0, 1, 1, 0, 0},
                    {0, 0, 0, 0, 0, 0, 0, 1},
                    {1, 1, 0, 1, 1, 0, 0, 0}};
 
    for(int i = 0; i < M; ++i) {
        for(int j = 0; j < M; ++j)
            std::cout << A[i][j] << ' ';
        std::cout << std::endl;
    }
    for(int i = 0; i < M; ++i)
        for(int j = 0; j < M; ++j)
            if(A[i][j] && ((j > 0 && !A[i][j - 1]) || (j == 0)) && ((i > 0 && !A[i - 1][j]) || (i == 0)))
                ++count;
    std::cout << count << std::endl;
    return 0;
}
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:36     Сколько прямоугольников в матрице #8
Ilot, здорово сделали, а я на своем варианте запоролся, когда начал делать
kitap
 Аватар для kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
21.03.2014, 10:16  [ТС]     Сколько прямоугольников в матрице #9
вот мое решение указанное верхнее решение очень помогло для решение этой задачи

Добавлено через 12 секунд
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
Uses crt;
label 1;
var
   a : array [1..100,1..100] of integer;
   i,j,s,n,st,i1,j1,c,p,t : Integer;
   b : Boolean;
begin
readLn(n);
for i:=1 to n do
    for j:=1 to n do read(a[i,j]);
    
b:=false;
while b<>true do
                begin
                for i:=1 to n do
                    for j:=1 to n do
                        if a[i,j]=1 then begin s:=i; inc(c); st:=j; p:=i;t:=j; goto 1; end;
                1:
                while a[s,st]<>0 do inc(s); dec(s);
                while a[s,st]<>0 do inc(st); dec(st);
                
                for i1:=p to s do
                    for j1:=t to st do a[i1,j1]:=0;
                    
                b:=true;
                for i:=1 to n do
                    for j:=1 to n do
                        if a[i,j]<>0 then b:=false;
                end;
writeln(c);
end.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
21.03.2014, 10:31     Сколько прямоугольников в матрице #10
Цитата Сообщение от kitap Посмотреть сообщение
вот мое решение
Цитата Сообщение от kitap Посмотреть сообщение
Код Pascal
Форум С++ для начинающих

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2014, 10:37     Сколько прямоугольников в матрице
Еще ссылки по теме:

C++ Выяснить сколько в массиве непересекающихся прямоугольников.
Даны стороны трех прямоугольников Найти периметры и площади этих прямоугольников C++
Объединение прямоугольников (количество объединенных прямоугольников минимально) C++

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

Или воспользуйтесь поиском по форуму:
kitap
 Аватар для kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
21.03.2014, 10:37  [ТС]     Сколько прямоугольников в матрице #11
когда я создавал тему необратил внимание на категорию форума и так получилось что я создал тема по категории с++ БезОбид

Добавлено через 59 секунд
зато задачку решили
Yandex
Объявления
21.03.2014, 10:37     Сколько прямоугольников в матрице
Ответ Создать тему
Опции темы

Текущее время: 08:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru