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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
kitap
 Аватар для kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
#1

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

13.03.2014, 14:38. Просмотров 573. Ответов 10
Метки нет (Все метки)

На квадратном клетчатом листе бумаги(размера МхМ клеток) нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются (см. пример).
Задан размер массива М. Затем построчно задается сам массив размером МхМ, в котором элемент 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++
C++ Для каждого элемента вектора определить, сколько раз он встречается в матрице
C++ вложенность прямоугольников
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
 Аватар для TenGen
97 / 95 / 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
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 07:43     Сколько прямоугольников в матрице #4
kitap, минут через 20 сяду к компу и скину вариант решения
ValeryS
Модератор
6449 / 4915 / 451
Регистрация: 14.02.2011
Сообщений: 16,296
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
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:09     Сколько прямоугольников в матрице #6
ValeryS, вы на самом деле думаете, что им по заданию требуют вот такие головоломки? Я считаю, что там вводятся только прямоугольные области
Ilot
Модератор
Эксперт С++
1780 / 1155 / 223
Регистрация: 16.05.2013
Сообщений: 3,042
Записей в блоге: 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
97 / 95 / 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
Модератор
6449 / 4915 / 451
Регистрация: 14.02.2011
Сообщений: 16,296
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++ Написать программу, определяющую, сколько нулей, положительных и отрицательных элементов находится в матрице
Метод прямоугольников C++
C++ Узнать сколько максимально прямоугольников можно составить из ветвей

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

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

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

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