Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

На квадратном клетчатом листе бумаги(размера МхМ клеток) нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются (см. пример).
Задан размер массива М. Затем построчно задается сам массив размером МхМ, в котором элемент A(i,j)=1, если клетка (i,j) принадлежит какому-либо прямоугольнику, и A(i,j)=0 в противном случае.
Сосчитать число прямоугольников в заданном массиве.


Пример
содержимое файла:
8
10000000
00011100
10011100
10011100
00000000
00001110
00001110
00000000
Ответ : 4 прямоугольника
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2014, 14:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сколько прямоугольников в матрице (C++):

Выяснить сколько в массиве непересекающихся прямоугольников. - C++
Привет всем. Дана задача(см.изображение). Вот я пытаюсь написать программу. #include <stdio.h> #include <stdlib.h> #include <conio.h>...

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

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

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

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

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

10
TenGen
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
13.03.2014, 16:17 #2
kitap, если действовать не особо думая (а я так и действовал), то можно тупо пробежаться по матрице. Если встречается 1, то счетчик прямоугольников увеличивается на 1, а все рядом стоящие единицы переименовываются в 0. Итого у нас останется матрица из 0 и количество найденных "полей" из единичек
2
kitap
5 / 5 / 0
Регистрация: 13.03.2014
Сообщений: 46
14.03.2014, 07:18  [ТС] #3
я так и хотел сделать но как мне сделать 0-ли рядом стояших единиц
0
TenGen
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 07:43 #4
kitap, минут через 20 сяду к компу и скину вариант решения
0
ValeryS
Модератор
6783 / 5191 / 496
Регистрация: 14.02.2011
Сообщений: 17,415
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
0
TenGen
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:09 #6
ValeryS, вы на самом деле думаете, что им по заданию требуют вот такие головоломки? Я считаю, что там вводятся только прямоугольные области
0
Ilot
Модератор
Эксперт С++
1825 / 1183 / 232
Регистрация: 16.05.2013
Сообщений: 3,119
Записей в блоге: 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;
}
2
TenGen
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
14.03.2014, 08:36 #8
Ilot, здорово сделали, а я на своем варианте запоролся, когда начал делать
0
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.
0
ValeryS
Модератор
6783 / 5191 / 496
Регистрация: 14.02.2011
Сообщений: 17,415
21.03.2014, 10:31 #10
Цитата Сообщение от kitap Посмотреть сообщение
вот мое решение
Цитата Сообщение от kitap Посмотреть сообщение
Код Pascal
Форум С++ для начинающих

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

Добавлено через 59 секунд
зато задачку решили
0
21.03.2014, 10:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2014, 10:37
Привет! Вот еще темы с ответами:

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

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

В матрице К размером m*n найти в каждом столбце произведение отрицательных элементов и количество нулевых элементов в матрице - C++
В матрице К размером m*n найти в каждом столбце произведение отрицательных элементов и количество нулевых элементов в матрице. Ребят,...

класс прямоугольников - C++
Составить описание класса прямоугольников со сторонами, параллельными осями координат. Предусмотреть возможность перемещения...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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