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

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

Восстановить пароль Регистрация
 
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
30.03.2013, 13:29     Задача "Цветная бумага" #1
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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
30.03.2013, 18:50     Задача "Цветная бумага" #2
Прежде всего сведите хадачу к однородной, считая что "дно" само лежит на бесконечной плоскости нулевого цвета и может накрыто или НЕ накрыто верхним прямоугольником.

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

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

Добавлено через 1 минуту
то есть у вас есть запрос llx, lly, urx, ury. если он не пересечется, то для него ответ просто площадь прямоугольника, если пересечется - вычесть кусочек. общий ответ как сумма ответов по запросам.
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
01.04.2013, 09:29  [ТС]     Задача "Цветная бумага" #4
salam, не могли бы помочь с алгоритмом, а то я вас не совсем понял.
alexcrz
3 / 3 / 1
Регистрация: 26.03.2013
Сообщений: 21
01.04.2013, 10:09     Задача "Цветная бумага" #5
прямоугольники могут и не перекрывать друг друга - рекурсия тут частный случай.
предлагаю в двумерный массив загнать номера цветов и с этим работать - тем более, что просят результать отсортировать по цветам и количеству занятых ячеек массива/площади.
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
01.04.2013, 14:36  [ТС]     Задача "Цветная бумага" #6
alexcrz, я так и сделал, загнал все в двумерный массив, но это работает медленно для больших чисел...
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.04.2013, 15:56     Задача "Цветная бумага" #7
у вас как отношения с STL?
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
= потерял
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 15:48     Задача "Цветная бумага"
Еще ссылки по теме:

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером C++
C++ Переменные "емкость", "Галлон", "Бензин"
Классы "Фигура", "Прямоугольник", "Круг" C++

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

Или воспользуйтесь поиском по форуму:
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");
}
Yandex
Объявления
04.04.2013, 15:48     Задача "Цветная бумага"
Ответ Создать тему
Опции темы

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