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

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

Войти
Регистрация
Восстановить пароль
 
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 434
#1

Задача "Цветная бумага" - C++

30.03.2013, 13:29. Просмотров 589. Ответов 8
Метки нет (Все метки)

N прямоугольников (1 ≤ N ≤ 1000) из цветной бумаги положили на лист белой бумаги шириной A и длиной B. Стороны прямоугольников параллельны сторонам листа. Все прямоугольники находятся в пределах границы листа и образуют фигуры разных цветов, если взглянуть сверху.
Начало системы координат (0, 0) совпадает с нижним левым углом листа белой бумаги, оси направлены по его сторонам.
Исходные данные
Порядок на вводе совпадает с тем, в котором положили на лист прямоугольники. Первая строка соответствует прямоугольнику «на дне». Первая строка содержит числа A, B и N через пробел (1 ≤ A, B ≤ 10000). Строки 2, …, N + 1 содержат по пять целых чисел: llx, lly, urx, ury, color: координаты нижнего левого и верхнего правого углов прямоугольника цвета color (1 ≤ color ≤ 2500). Белый лист имеет цвет 1.
Результат
Выведите список всех цветов, которые видны сверху, вместе с общей видимой площадью каждого цвета. Список должен быть упорядочен по цвету. Не нужно выводить цвета с нулевой видимой площадью.

исходные данные
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
результат
1 91
2 84
3 187
4 38

Я пытался взять поле A на B и отмечать на нем прямоугольники цветами, а потом подсчитывал количество клеток. Но для больших полей все будет просчитываться очень долго. Помогите реализовать более быстрый алгоритм.
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>
 
using namespace std;
 
struct Rec{
    signed short col;
    long area;
}; 
 
int main(){
    ifstream in("input.txt");
    ofstream out("output.txt");
    
    signed short a, b, n, llx, lly, urx, ury, col;
    signed short **from;
    Rec *arr;
 
    in >> a >> b >> n;
 
    from = new signed short*[a];
    for(register signed short j = 0; j < a; j++){
        from[j] = new signed short[b];
        for(register signed short i = 0; i < b; i++) from[j][i] = 1;
    }
 
    arr = new Rec[n + 1];
 
    arr[0].area = 0;
    arr[0].col = 1;
    for(register signed short q = 1; q < n + 1; q++){
        arr[q].area = 0;
        in >> llx >> lly >> urx >> ury >> col;
        arr[q].col = col;
        for(register signed short j = lly; j < ury; j++)
            for(register signed short i = llx; i < urx; i++) from[j][i] = col;
    }
 
    for(register signed short j = 0; j < a; j++)
        for(register signed short i = 0; i < b; i++)
            for(register signed short q = 0; q < n + 1; q++)
                if(from[j][i] == arr[q].col){
                    arr[q].area++;
                    break;
                }
 
    for(register signed short q = 0; q < n + 1; q++){
        out << arr[q].col << ' ' << arr[q].area;
        if(q != n) out << '\n';
    }
 
    delete []arr;
 
    for(register signed short j = 0; j < b; j++) delete []from[j];
    delete []from;
 
    in.close();
    out.close();
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2013, 13:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача "Цветная бумага" (C++):

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include &lt;iostream&gt; using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в &quot;0x76f015de&quot; в &quot;контрольная 1 задача 2.exe&quot;: 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Написать программу для игры "Камень, бумага, ножницы" - C++
Прочитал четыри главы книги Бьярне Страуструп Программирование: принципы и практика использования C++, исправленное издание и приступил...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Решение задачи "отобразить широту в десятичный формат" "Стивен Прата 6-е издание. Лекции и упражнение" 3 глава 3 задача - C++
Напишите программу, которая запрашивает широту в градусах, минутах и секундах, после чего отображает широту в десятичном формате. В одной...

8
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
30.03.2013, 18:50 #2
Прежде всего сведите хадачу к однородной, считая что "дно" само лежит на бесконечной плоскости нулевого цвета и может накрыто или НЕ накрыто верхним прямоугольником.

Далее, если представить, что цветных слоев всего два, то верхний слой виден целиком, а из площади нижнего цвета вычитается площадь перекрывающего его верхнего цвета.

А теперь делаете все это рекурсивно: из самого верхнего слоя ничего не вычитается, из следующего - область перекрытия его верхним, из третьего - область перекрытия его вторым + то, что от первого выходит за рамки второго итд.
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
30.03.2013, 20:15 #3
кажется, что если посортить все запросы по координатам, сохранив порядок следования, и считать ответ для каждого запроса в отдельности, то можно за O(n*logn) все сделать.

Добавлено через 1 минуту
то есть у вас есть запрос llx, lly, urx, ury. если он не пересечется, то для него ответ просто площадь прямоугольника, если пересечется - вычесть кусочек. общий ответ как сумма ответов по запросам.
0
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 434
01.04.2013, 09:29  [ТС] #4
salam, не могли бы помочь с алгоритмом, а то я вас не совсем понял.
0
alexcrz
3 / 3 / 1
Регистрация: 26.03.2013
Сообщений: 21
01.04.2013, 10:09 #5
прямоугольники могут и не перекрывать друг друга - рекурсия тут частный случай.
предлагаю в двумерный массив загнать номера цветов и с этим работать - тем более, что просят результать отсортировать по цветам и количеству занятых ячеек массива/площади.
0
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 434
01.04.2013, 14:36  [ТС] #6
alexcrz, я так и сделал, загнал все в двумерный массив, но это работает медленно для больших чисел...
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
01.04.2013, 15:56 #7
у вас как отношения с STL?
0
alexcrz
3 / 3 / 1
Регистрация: 26.03.2013
Сообщений: 21
01.04.2013, 19:32 #8
Как отсортировать вектор векторов и найти повторы буду изучать завтра - по картинке результат вроде похож на правду

Еще дурная мысль - запомнить цвета и искать их количество в векторе, а не все 2500. Тогда сортировка не нужна - просто перебрать. Хотя при большом количестве наложений и малой площади лучше все же сортировка.

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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i > 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl;
    system ("pause");
}
Добавлено через 10 минут
в 22 строке i >= 0
= потерял
0
alexcrz
3 / 3 / 1
Регистрация: 26.03.2013
Сообщений: 21
04.04.2013, 15:48 #9
Если целиком, то как-то так... была мысль начинать искать следующий цвет после непрерывного повторения предыдущего... не получилость

1111111111111111111
111112222222222..

то есть начинать со второго ряда, с середины.


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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i >= 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl << endl;
    
 
    int count = 0, color_chk = -1;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
 
                for (int i = 0; i < xtotal; i++)
                for (int j = 0; j < ytotal; j++)
                    if (color_chk == y[i][j])
                    {
                        count++;
                        y[i][j] = -1;
                    }
 
                cout << color_chk << " " << count << endl;
            } 
        }
    
system ("pause");
}
Добавлено через 1 час 27 минут
Wanee. решил ваш код изучит (до этого не смотрел). Я так понял, что цвета отдельно в массиве и его надо еще очистить от дублей?

Подал на вход

20 20 3
2 2 18 18 2
0 8 19 19 2
8 0 10 19 4

получил

1 91
2 271
2 0
4 38

Вопрос.
Как начать просматривать двумерный массив с конкретного места array[x][y], где x и y при первом заходе на просмотр равны нулям, а при последующих - изменяются по результату просмотра.

Если конкретно по задаче. Я просмотрел 578 рядов по 10000 цветов в каждом. Так как я перебираю цвета по порядку - в этих рядах ничего интересного для меня нет. В коде я заменил их содержимое на -1. Но зачем мне сравнивать эти 5780000 "минус единиц" с еще не просеянным цветом в следующей 579-й строке?

Добавлено через 1 час 42 минуты
Разобрался вроде сам. Количество операций при сверке конкретного цвета со всем массивом уменьшилось с 400 до 80 при данном вводе значений. Помогло ли это сократить время выполнения на больших объемах?

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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i >= 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl << endl;
    
 
    int count = 0, color_chk = -1, cycle = 0, ichk = 0, jchk = 0, xchk = 0, ychk = 0, end = 0;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
                xchk = ichk;
                ychk = jchk;
                end = 0;
 
                for (int i = 0; i < xtotal; i++)
                {cycle++;
                        if (xchk > 0) {i = xchk; xchk = -1;} 
                        for (int j = 0; j < ytotal; j++)
                        {
                            if (ychk > 0) {j = ychk; ychk = -1;}
                            if (color_chk == y[i][j])
                            {
                                
                                count++;
                                if (end ==0) {ychk++;
                                if (ychk == ytotal) {jchk = 0; ychk++;}}
                                y[i][j] = -1;
                            } else end = -1;
                        }
                }
 
                cout << color_chk << " " << count << endl;
            } 
        }
    cout << "total operations: " << cycle << endl;
system ("pause");
}
Добавлено через 1 час 1 минуту
9 и 10 строку надо изменить, перепутал x c y... иначе возможен выход за пределы вектора
C++
1
2
vector<int> x(ytotal, 1);
    vector<vector<int>> y(xtotal, x);


в 22-25 заменить цифры на константы, если нужена демонстрация и хотите изменить размер нижнего основного листа

C++
1
2
3
4
for (int i=(xtotal-1); i >= 0; i--)
    { cout << endl;
        for (int j=0; j < ytotal; j++)  
                cout << y[j][i];
Добавлено через 21 час 32 минуты
Добавил определение позиции очередного цвета в циклах t1 и t2.
Исправил "начальную позицию" с которой он будет сравниваться в циклах i и j.
Данные читаются и записываются в файлы input.txt и output.txt

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
#include <iostream>
#include <vector>
#include <fstream>
#include <stdlib.h>
using namespace std;
 
 
int main()
{ 
// Заполнение вектора ----------------------------------------------------------------
 
    int xtotal = 0, ytotal = 0, q=0;
    
    int x1, y1, x2, y2, color;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in >> xtotal >> ytotal >> q;
    vector<int> x(ytotal, 1);
    vector<vector<int>> y(xtotal, x);
    do
    {
        in >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
 
// Вывод на экран. При больших xtotal и ytotal может не влезть  
 
    for (int j=(ytotal - 1); j >= 0; j--)
    { 
        cout << endl;
        for (int i = 0; i < xtotal; i++)
            cout << y[i][j];
    }
    cout << endl << endl;
    
// Берем цвет по очереди и сравниваем со элементами вектора, которые идут после. Провереные цвета переименовываем в -1. 
 
    int count = 0, color_chk = -1, cycle = 0, ichk = 0, jchk = 0, xchk = 0, ychk = 0, end = 0;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
                xchk = ichk;
                ychk = jchk;            
                end = 0;
 
                for (int i = 0; i < xtotal; i++)
                {
                        if (xchk > 0) {i = xchk; xchk = -1;} 
                        for (int j = 0; j < ytotal; j++)
                        {
                            if (ychk > 0) {j = ychk; ychk = -1;}
                            if (color_chk == y[i][j])
                            {
                                
                                count++;
                                if (end == 0) {jchk++;
                                if (jchk == ytotal) {jchk = 0; ichk++;}}
                                y[i][j] = -1;
                            } else end = -1;
                        }
                }
 
 
                out << color_chk << " " << count << endl;
                t1 = ichk;
                t2 = jchk;              
            } 
        }
    
    in.close();
    out.close();
    system("pause");
}
0
04.04.2013, 15:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 15:48
Привет! Вот еще темы с ответами:

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...


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

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

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