54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
1

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

30.03.2013, 13:29. Показов 1996. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.03.2013, 13:29
Ответы с готовыми решениями:

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

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

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

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

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

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

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

Добавлено через 1 минуту
то есть у вас есть запрос llx, lly, urx, ury. если он не пересечется, то для него ответ просто площадь прямоугольника, если пересечется - вычесть кусочек. общий ответ как сумма ответов по запросам.
0
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
01.04.2013, 09:29  [ТС] 4
salam, не могли бы помочь с алгоритмом, а то я вас не совсем понял.
0
13 / 16 / 5
Регистрация: 26.03.2013
Сообщений: 142
01.04.2013, 10:09 5
прямоугольники могут и не перекрывать друг друга - рекурсия тут частный случай.
предлагаю в двумерный массив загнать номера цветов и с этим работать - тем более, что просят результать отсортировать по цветам и количеству занятых ячеек массива/площади.
0
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
01.04.2013, 14:36  [ТС] 6
alexcrz, я так и сделал, загнал все в двумерный массив, но это работает медленно для больших чисел...
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
01.04.2013, 15:56 7
у вас как отношения с STL?
0
13 / 16 / 5
Регистрация: 26.03.2013
Сообщений: 142
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
13 / 16 / 5
Регистрация: 26.03.2013
Сообщений: 142
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.04.2013, 15:48
Помогаю со студенческими работами здесь

Игра "камень ножницы бумага"
решил написать игру камень ножницы бумага но всё работает кроме самой логики игры он не выводит...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются...

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

Задача "замочная скважина" и "ключ" ошибка в коде
Почему-то не работает программа реализующая следующую задачу: Даны мозаичные изображения...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru