Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
 Аватар для Garred
282 / 80 / 7
Регистрация: 19.04.2011
Сообщений: 223

Задача о прямоугольниках С++

22.10.2011, 07:14. Показов 2581. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Уважаемые форумчане,помогите решить следующую задачу

На клеточном листе бумаги размером MхN расположены прямоугольники. Задан массив MхN в котором элемент a[i,j]=1 если клетка листа (i,j) яв-ся частью прямоугольника, и a[i,j]=0 если это пустая клетка. Напечатать число прямоугольников

При этом матрица MxN записана в текстовом файле с расширением .in
Количество прямоугольников выводится в текстовый файл .out

Заранее благодарю.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.10.2011, 07:14
Ответы с готовыми решениями:

Задача о квадратах и прямоугольниках
Даны целые положительные числа A, B, C. На прямоугольнике размера A  B размещено максимально возможное количество квадратов со стороной C...

Выводить пикселы в прямоугольниках, расположенных: в левой нижней четверти экрана
Выводить пикселы в прямоугольниках, расположенных: в левой нижней четверти экрана (использовать яркие цвета), в правой верхней четверти...

Олимпиадная задача по программированию. PascalABC.NET. Задача L. Переключение между окнами
Когда пользователь работает в операционной системе Winux, у него часто запущено несколько приложений. Каждое из приложений работает в...

12
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.10.2011, 10:34
Garred, ссылку на условие задачи можете дать? Условие вроде корректное, но на всякий случай хочется его проверить.
1
 Аватар для Garred
282 / 80 / 7
Регистрация: 19.04.2011
Сообщений: 223
22.10.2011, 13:47  [ТС]
valeriikozlov, ссылки нет. Слово в слово списал условие из сборника задач, который преподаватель дал на паре на пять минут, и не знаю ни названия, ни издательства книги.

Добавлено через 4 минуты
Цитата Сообщение от Garred Посмотреть сообщение
При этом матрица MxN записана в текстовом файле с расширением .in
Количество прямоугольников выводится в текстовый файл .out
Эти условия я написал от себя как требования предъявленные преподавателем к лабораторным
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.10.2011, 14:16
Garred, Тогда уточняю, прямоугольники могут касаться друг друга сторонами или нет? Если да, то может возникнуть неоднозначность. Если нет, то все очень будет просто.
0
 Аватар для Garred
282 / 80 / 7
Регистрация: 19.04.2011
Сообщений: 223
22.10.2011, 14:29  [ТС]
valeriikozlov, прямоугольники не касаются.

Пример входных данных

1 1 1 0 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 0 1 1 0 0
1 1 0 0 1 1 0 1
1 1 0 0 1 1 0 1
0 0 0 0 0 0 0 0

выход 4
0
 Аватар для Mayonez
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
22.10.2011, 15:15
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <fstream>
#include <vector>
 
using namespace std;
 
void removeRectangle(int x, int y, vector<vector<bool> > &v)
{
    v[x][y] = 0;
    struct
    {
        int x;
        int y;
    } moves[] =
    {
        { 0,  1},
        { 0, -1},
        { 1,  0},
        {-1,  0}
    };
    for(size_t i = 0; i < sizeof moves / sizeof *moves; i++)
    {
        const int nx = x + moves[i].x;
        const int ny = y + moves[i].y;
        if(nx >= 0 && nx < v.size() &&
            ny >= 0 && ny < v[nx].size() && v[nx][ny])
            removeRectangle(nx, ny, v);
    }
}
 
int main()
{
    ifstream fin("input.in");
    vector<vector<bool> > field;
    vector<bool> lines;
    while(!fin.eof())
    {
        char ch = fin.get();
        if(ch == ' ')
            continue;
        if(ch == '\n')
        {
            field.push_back(lines);
            lines.clear();
            continue;
        }
        lines.push_back(ch - '0');
    }
 
    int counter = 0;
    for(size_t i = 0; i < field.size(); i++)
        for(size_t j = 0; j < field[i].size(); j++)
            if(field[i][j])
            {
                removeRectangle(i, j, field);
                counter++;
            }
    ofstream fout("output.out");
    fout << counter << endl;
    return 0;
}
Добавлено через 1 минуту
не самый эффективный вариант, зато рабочий
2
290 / 193 / 23
Регистрация: 03.08.2011
Сообщений: 2,824
Записей в блоге: 12
22.10.2011, 15:27
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
31
32
33
34
35
#include "stdlib.h"
#include "time.h"
#include "conio.h"
#include "stdio.h"
 
 
 
int main()
{
    srand(time(NULL));
    int xt[100],yt[100];
    int kolvo=0 ,ya_odin[100];
    int i,i2;
    for(i=0;i<100;i++)
    {
        *(xt+i)=rand() %798+1;
        *(yt+i)=rand() %478+1;
        ya_odin[i]=0;
   
    }
     
    for(i=0;i<100;i++)
    {
        for(int i2=0;i2<100;i2++)
            if(xt[i]-1==xt[i2] || xt[i]+1==xt[i2] || 
            yt[i]-1==yt[i2] || yt[i]+1==yt[i2] && ya_odin[i]==0)
            {
                ya_odin[i]=1;    
                kolvo++;
            }
    }
    printf("%d", kolvo);
    getch();
    return 0;
}
1
 Аватар для Garred
282 / 80 / 7
Регистрация: 19.04.2011
Сообщений: 223
22.10.2011, 15:34  [ТС]
Van111, могли бы Вы прокомментировать свой код?
0
290 / 193 / 23
Регистрация: 03.08.2011
Сообщений: 2,824
Записей в блоге: 12
22.10.2011, 16:00
Garred,
я не уверен что он точно работает ну щас попробую

Добавлено через 8 минут
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
31
32
33
34
35
36
#include "stdlib.h"
#include "time.h"
#include "conio.h"
#include "stdio.h"
 
 
 
int main()
{
    srand(time(NULL));// вот она помоему подводит(функция)
    int x[100],y[100];// у точки есть кординаты х и у
    int kolvoPram=0 ,ya_odin[100];//ya_odin если равно 0 то точка не с кем не соприкасается
    int i,i2;// переменные для циклов
    for(i=0;i<100;i++)
    {
        x[i])=rand() %798+1; //вот размеры поля
        y[i]=rand() %478+1; //вот размеры поля
        ya_odin[i]=0;
   
    }
     
    for(i=0;i<100;i++)// вот движок мне кажется он подводит
    {
        for(int i2=0;i2<100;i2++)
            if((x[i]-1==x[i2] || x[i]+1==x[i2] || 
            y[i]-1==y[i2] || y[i]+1==y[i2]) && ya_odin[i]==0)
            {
                printf("%d %d --- %d %d  ",x[i],y[i],x[i2],y[i2]); //печатает точки которые соприкасаются
                ya_odin[i]=0;    
                kolvoPram++;
            }
    }
    printf("%d", kolvoPram);
    getch();
    return 0;
}
1
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.10.2011, 18:34
Лучший ответ Сообщение было отмечено как решение

Решение

Цитата Сообщение от Garred Посмотреть сообщение
valeriikozlov, прямоугольники не касаются.
На самом деле проще (и быстрее) в этом случае подсчитать кол-во верхних левых вершин прямоугольников.
Допустим имеем массив mas[M][N] заполненный нулями и единицами, тогда так:
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
int col=0;
for(int i=0; i<M; i++)
    for(int j=0; j<N; j++)
        if(mas[i][j]==1)
        {
            if(i==0)
            {
                if(j==0)
                    col++;
                else
                {
                    if(mas[i][j-1]==0)
                        col++;
                }
            }
            else
            {
                if(j==0)
                {
                    if(mas[i-1][j]==0)
                        col++;
                }
                else
                {
                    if(mas[i][j-1]==0 && mas[i-1][j]==0)
                        col++;
                }
            }
        }
 // вот здесь в переменной col находится нужный результат
4
290 / 193 / 23
Регистрация: 03.08.2011
Сообщений: 2,824
Записей в блоге: 12
22.10.2011, 18:38
valeriikozlov, почему вы ещё форумчанин вам в эксперты с++ надо
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
23.10.2011, 01:36
Лучший ответ Сообщение было отмечено как решение

Решение

Цитата Сообщение от valeriikozlov Посмотреть сообщение
На самом деле проще (и быстрее) в этом случае подсчитать кол-во верхних левых вершин прямоугольников.
Тоже пришла такая мысль. Реализовал так:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/////////////////////////////////////////////////////////////////////////////////////////
//На клеточном листе бумаги размером MхN расположены прямоугольники. 
//Задан массив MхN в котором элемент a[i,j]=1 если клетка листа (i,j) 
//яв-ся частью прямоугольника, и a[i,j]=0 если это пустая клетка. 
//Напечатать число прямоугольников.
/////////////////////////////////////////////////////////////////////////////////////////
//В моей реализации нули и единицы в исходный файл записывать без пробелов.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef std::vector<T_str>  T_strings;
/////////////////////////////////////////////////////////////////////////////////////////
bool  is_left_upper_corner
    (
        const T_strings&    strings, 
        int                 i, 
        int                 j
    )
{
    return      strings[i][j]               == '1'
 
            &&  (
                        i                   ==  0 
                    ||  strings[i - 1][j]   == '0'
                )
 
            &&  (
                        j                   ==  0
                    ||  strings[i][j - 1]   == '0'
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
void  count_rectangles
    (
        const T_str&  ifilename, 
        const T_str&  ofilename
    )
{
    std::ifstream  ifile( ifilename.c_str() );
    if( !ifile )
    {
        std::cout << "Невозможно открыть файл \""
                  << ifilename
                  << "\"."
                  << std::endl;
    }
 
    T_strings   strings;
    std::copy
        (
            std::istream_iterator<T_str>    (ifile),
            std::istream_iterator<T_str>    (),
            std::back_inserter              (strings)
        );
 
    int  counter = 0;
    for(int  i = 0; i < strings.size(); ++i)
    {
        for(int  j = 0; j < strings[i].size(); ++j)
        {            
            if( is_left_upper_corner(strings, i, j) )
            {
                ++counter;
            }
        }
    }
    std::ofstream  ofile( ofilename.c_str() );
    ofile << counter;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const T_str  ifilename = "if.txt";  
    const T_str  ofilename = "of.txt";
    count_rectangles(ifilename, ofilename);
}
3
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.10.2011, 09:06
Быдлокод, зато для массива достаточно m байт памяти.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <fstream>
 
int q, n, m, j, c, i;
 
int main()
{
    std::fstream v("input.txt"), o("output.txt", std::ios::out);
    
    v >> n >> m;
    
    char * w = new char[m];
    
    for ( ; v >> q; ++j)
    {
            i = j % m;
            c += q && ( !i || !w[i - 1] ) && ( j < m || !w[i] );
            w[i] = q;
    }
    delete[] w;        
    o << c;
}
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
23.10.2011, 09:06
Помогаю со студенческими работами здесь

Васильев C# Глава 8 задача 2 (Просьба объяснить формулировку(задача внутри)
Текст задачи Написать программу , в которой есть класс с полем, являющимся ссылкой на одномерный целочисленный массив. У класса есть...

В некотором государстве ввели компьютерный паспорт гражданина. Укажите пол гражданина и последовательность событий
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Васильев C# Глава 7 задача 8 (Просьба объяснить формулировку(задача внутри)
Текст задачи Напишите программу с классом, у которого есть текстовое поле. Значение текстовому полю присваивается при создании объекта...

Считалка. Олимпиадная задача по программированию
Ирочка попросила маму придумать новую считалочку. Мама тут же ей &quot;выдала&quot;. Пусть в кругу N человек. Это число N будем изменять...

Задача на k-тую цифру последовательности, задача на схему Горнера.
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru