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

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

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

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

13.03.2014, 14:38. Просмотров 616. Ответов 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++
Привет всем. Дана задача(см.изображение). Вот я пытаюсь написать программу. #include <stdio.h> #include <stdlib.h> #include <conio.h>...

Узнать сколько максимально прямоугольников можно составить из ветвей - C++
После подвижных игр ученики 9-А класса решили поиграть во что-то спокойное. С ветвей, остались после игры в кольцо, они захотели составить...

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

Для каждого элемента вектора определить, сколько раз он встречается в матрице - C++
Дана целочисленная матрица A(N,M) и целочисленный вектор D(K). Для каждого элемента вектора определить, сколько раз он встречается в...

Написать программу, определяющую, сколько нулей, положительных и отрицательных элементов находится в матрице - C++
Написать программу, определяющую, сколько нулей, сколько положительных и сколько отрицательных элементов находится в каждом столбце...

Определить, где и на сколько больше элементов, равных минимальному - в заданной матрице или в заданном массиве - C++
Заданы матрица и массив. Подразумевается, что в них может быть несколько элементов, значение которых равно минимальному. Определить, где и...

У меня задача,в матрице,заменить первый отрицательный элемент максимальным элементом. Проходить по матрице слева направо,сверху вниз - C++
У меня задача,в матрице,заменить первый отрицательный элемент максимальным элементом. Проходить по матрице слева направо,сверху вниз. Я...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
13.03.2014, 16:17     Сколько прямоугольников в матрице #2
kitap, если действовать не особо думая (а я так и действовал), то можно тупо пробежаться по матрице. Если встречается 1, то счетчик прямоугольников увеличивается на 1, а все рядом стоящие единицы переименовываются в 0. Итого у нас останется матрица из 0 и количество найденных "полей" из единичек
kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
14.03.2014, 07:18  [ТС]     Сколько прямоугольников в матрице #3
я так и хотел сделать но как мне сделать 0-ли рядом стояших единиц
TenGen
Будущее рядом
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 07:43     Сколько прямоугольников в матрице #4
kitap, минут через 20 сяду к компу и скину вариант решения
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
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
Будущее рядом
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:09     Сколько прямоугольников в матрице #6
ValeryS, вы на самом деле думаете, что им по заданию требуют вот такие головоломки? Я считаю, что там вводятся только прямоугольные области
Ilot
Модератор
Эксперт С++
1807 / 1164 / 226
Регистрация: 16.05.2013
Сообщений: 3,060
Записей в блоге: 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
Будущее рядом
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:36     Сколько прямоугольников в матрице #8
Ilot, здорово сделали, а я на своем варианте запоролся, когда начал делать
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
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
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++
Здраствуйте!я начинающий на с/с++ написал программу которая вычисляет площадь пересечения прямоугольников,вылазит ошибка:scratch: ...

Метод прямоугольников - C++
Здравствуйте! Есть выражение: y = −2^2 + 3x + 6, y = x + 2. Использовать метод прямоугольников. Для построения прямоугольника...

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

Пересечение прямоугольников - C++
В прямоугольной системе координат (оси расположены слева направо и сверху вниз) заданы два прямоугольника (стороны параллельны осям). Найти...


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

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

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

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