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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Demon55
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 42
29.11.2013, 08:58     Посчитать количество прямоугольников, заданных черным цветом #1
С++ изучаю несколько месяцев и есть проблемы с синтаксисом и пониманием=)
Не совсем понятно что от меня требуют?
И не знаю как реализовать решение данной задачи.
Заранее благодарен, за помощь.

Собственно, задача:
Прямоугольное поле m на n разбито на mn квадратных клеток. Некоторые клетки покрашены в черный цвет. Известно, что все черные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин черных прямоугольников. Считая, что цвета клеток даны в виде массива типа arr [m] [n], где каждый элемент равен единице только тогда когда эта клетка черная, если она белая, то элемент массива равен 0, подсчитать число черных прямоугольников.
Прим. Число прямоугольников равно числу их левых верхних углов. Является ли клетка верхним углом, можно узнать, посмотрев на ее цвет, а так же цвет верхнего и левого соседей.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2013, 08:58     Посчитать количество прямоугольников, заданных черным цветом
Посмотрите здесь:

C++ Посчитать количество знаков препинания в тексте и вывести их количество.
C++ Посчитать количество смен знаков заданных чисел массива
C++ Посчитать количество строчных и количество прописных букв
C++ В текстовом файле посчитать количество заданных букв
C++ Посчитать количество заданных букв в файле
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ПерС
366 / 282 / 84
Регистрация: 05.11.2013
Сообщений: 806
Записей в блоге: 5
Завершенные тесты: 1
29.11.2013, 09:10     Посчитать количество прямоугольников, заданных черным цветом #2
От тебя требуют найти все кораблики в "Морском бое"
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
29.11.2013, 09:15     Посчитать количество прямоугольников, заданных черным цветом #3
А мне подумалось, что то типа вот такого:

Посчитать количество прямоугольников, заданных черным цветом
Demon55
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 42
29.11.2013, 09:21  [ТС]     Посчитать количество прямоугольников, заданных черным цветом #4
Цитата Сообщение от SatanaXIII Посмотреть сообщение
А мне подумалось, что то типа вот такого:
Вложение 334924
Прямоугольники вроде как не должны пересекаться.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
29.11.2013, 09:31     Посчитать количество прямоугольников, заданных черным цветом #5
Цитата Сообщение от Demon55 Посмотреть сообщение
Прямоугольники вроде как не должны пересекаться.
Да, действительно.
Но от диагонального размещения условия не страхуют.

P.S. Еще я не понял про примечание.
Demon55
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 42
29.11.2013, 09:42  [ТС]     Посчитать количество прямоугольников, заданных черным цветом #6
Опишу как понял эту задачу я:
Размер поля вводим с консоли (как раз те m и n), все поле заполнено 0, а в разных участках поля располагаются прямоугольники из 1, нужно посчитать кол-во прямоугольников.
Не пойму какого размера прямоугольники и сколько их должно быть на поле.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
29.11.2013, 10:09     Посчитать количество прямоугольников, заданных черным цветом #7
Цитата Сообщение от Demon55 Посмотреть сообщение
Размер поля вводим с консоли
Вряд ли. Слишком геморное тестирование будет. Вот же:
Цитата Сообщение от Demon55 Посмотреть сообщение
Считая, что цвета клеток даны в виде массива
Для простоты можно прям в программе забивать. Обычно подобные задания не на умения ввода с консоли. )
C++
1
2
3
4
5
6
7
const int n = 6, m = 5;
int arr[n][m] = { { 1, 1, 1, 0, 0 },
                  { 1, 0, 1, 0, 0 },
                  { 1, 0, 1, 0, 0 },
                  { 1, 1, 1, 0, 0 },
                  { 0, 0, 0, 1, 1 },
                  { 0, 0, 0, 1, 1 } };
Добавлено через 2 минуты
Вот здесь поглядите. Я там выводил алгоритм.
Найти площадь крупнейшего сплошного прямоугольника суши
Stingo
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 10
29.11.2013, 10:34     Посчитать количество прямоугольников, заданных черным цветом #8
Если я правильно понял, по условию задачи предпологается, что прямоугольники всегда расставлены правильно, то есть варианты типо такого:
C++
1
2
3
4
5
6
{ 1, 1, 1, 1, 0 },
{ 1, 0, 1, 1, 0 },
{ 1, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 1 }
исключены.
Соответственно, согласно примечанию ищем углы проверяем левый и верхний элемент массива и при положительном исходе инкреминируем счетчик:
C++
1
2
3
4
5
6
7
8
9
10
11
12
//задаем массив и счетчик
int arr [n][m] = {...};
int sum = 0;
//сам поиск
for (int i = 0; i < n; i++) 
{
    for (int j = 0; j < m; j++) 
    {
            if (arr[i][j]==1 && arr[i-1][j]==0 && arr[i][j-1]==0) sum++;
        }
}
cout << "число прямоугольников: " << sum;
Demon55
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 42
29.11.2013, 14:39  [ТС]     Посчитать количество прямоугольников, заданных черным цветом #9
SatanaXIII, ваш алгоритм показался слишком сложным.

Stingo
Я попробовал ваш вариант, но работает не совсем корректно.
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
#include "stdafx.h"
#include <stdio.h>
#include "conio.h"
#include <locale.h>
#include <cstdlib>
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{setlocale(LC_ALL, "Russian");
const int n = 7, m = 8;
int arr[n][m] = { { 1, 1, 1, 0, 0, 0, 0, 0 },
                  { 1, 1, 1, 0, 0, 0, 0, 0 },
                  { 1, 1, 1, 0, 0, 0, 0, 0 },
                  { 0, 0, 0, 0, 0, 0, 0, 0 },
                  { 0, 0, 0, 1, 1, 1, 0, 0 },
                  { 0, 0, 0, 1, 1, 1, 0, 0 },
                  { 0, 0, 0, 1, 1, 1, 0, 0 } };
    
int sum = 0;
for (int i = 0; i < n; i++) 
{
    for (int j = 0; j < m; j++) 
    {
            if (arr[i][j]==1 && arr[i-1][j]==0 && arr[i][j-1]==0) sum++;
        }
}
printf("Число прямоугольников %d\n ", sum);
system("pause");
    return 0;
}
Stingo
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 10
29.11.2013, 15:14     Посчитать количество прямоугольников, заданных черным цветом #10
А, ну это из-за нулевых значений индексов, если i и/или j равны нолю, то i-1 и/или j-1 не работают.
Ну соответственно проверку нулевых значений индексов добавить надо, хотя бы так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < n; i++) 
{
    for (int j = 0; j < m; j++) 
    {
            if (arr[i][j]==1)
            {
                if (i>0 && j>0 && arr[i-1][j]==0 && arr[i][j-1]==0) sum++;
                if (i==0 && j>0 && arr[i][j-1]==0) sum++;
                if (j==0 && i>0 && arr[i-1][j]==0) sum++;
                if (j==0 && i==0) sum++;
            } 
        }
}
Demon55
1 / 1 / 0
Регистрация: 29.11.2013
Сообщений: 42
29.11.2013, 16:44  [ТС]     Посчитать количество прямоугольников, заданных черным цветом #11
Всем спасибо, за помощь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2015, 13:14     Посчитать количество прямоугольников, заданных черным цветом
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
вадим 353
0 / 0 / 0
Регистрация: 08.12.2015
Сообщений: 5
20.12.2015, 13:14     Посчитать количество прямоугольников, заданных черным цветом #12
можете пожалуйста в делфи написать прогу эту..
Yandex
Объявления
20.12.2015, 13:14     Посчитать количество прямоугольников, заданных черным цветом
Ответ Создать тему
Опции темы

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