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

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

Войти
Регистрация
Восстановить пароль
 
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

Паркет - C++

01.09.2010, 14:46. Просмотров 874. Ответов 9
Метки нет (Все метки)

есть паркет (см. рисунок) даны кординати нижней левой и правой верхней точки (в даном случае 4 4 и 12 10) закрашеной области. нужно определить сколько внутри этой области прямоугольников 1х1, 1х2, 1х3, 1х4, 1х5. в даном случае 6 1 0 0 8 соответственно. закрашеная область может быть произвольной
0
Миниатюры
Паркет  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2010, 14:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Паркет (C++):

Графика(нарисовать паркет) - C++
Кто нибудь может скинуть графику на си или паскале, вида "паркет"

Нарисовать паркет с помощью процедуры - Pascal ABC
Нарисовать паркет с помощью процедуры

Циклическое размножение фигур. Паркет - Turbo Pascal
Пожалуйста нарисуйте в паскале 4 рисунка: 1. простой рисунок 2. рисунок через процедуру 3. рисунок движущийся 4. рисунок через цикл...

Нарисовать паркет, используя процедуры - Pascal ABC
Нарисовать паркет с помощью процедуры

Нарисовать правильный двухцветный паркет по универсальному алгоритму - Pascal ABC
Нарисовать правильный двухцветный паркет по универсальному алгоритму. (паркет выглядит как сложенные между собой шестиугольники двух цветов

Написать программу, рисующую на экране паркет из прямоугольников и кружочков - PascalABC.NET
Написать программу, рисующую на экране паркет из прямоугольников и кружочков.

9
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
01.09.2010, 16:42 #2
Предлагаю свою подсказку.

Имеем одномерный массив A[80], элементы которого соответствуют белым прямоугольникам 1x5. Значение элемента - это количество квадратиков 1x1, которые попали под зеленую область.
Имеем двухмерный массив B[20][20], элементы которого соответсвуют квадратикам 1x1 из данного поля (или паркета). Значение элемента - это указатель на соответствующий элемент из массива A[80]. Пример: B[0][i], где i от 0 до 4, должен указывать на A[0].

Если что-то из подсказки не понятно - спрашиваем.
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
01.09.2010, 21:15  [ТС] #3
Евгений М.,
одни прямоугольники вертикальные, другие - горизонтальные -- как различать

Добавлено через 3 часа 58 минут
больше никаких идей нет ни у кого??? хотя бы что нибудь...
0
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
01.09.2010, 21:34 #4
Итак.

Задача номер один - получить список всех "плиток", к-рые закрашены. Дальше задачу разбиваем на подзадачи по 1й плитке.

Номер два: получаем пересечение плитки и закрашенной области. Получится закрашенная область только для этой плитки.

Номер три: Смотрим ширину и высоту пересекаемой области. 2х6 - это либо две шестёрки, либо шесть двоек.
Что из них - очень просто. Если сумма индексов плитки парная - она горизонтальная. И наоборот.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
01.09.2010, 23:33 #5
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
#include <map>
#include <set>
#include <iostream>
 
typedef std::map<int, int>  T_count_map;
 
struct T_point
{
    int x;
    int y;
};
 
void count_parket(T_point left_below, T_point right_above)
{
    T_count_map  count_map;
    for(int x = left_below.x; x < right_above.x; ++x)
    {
        for(int y = left_below.y; y < right_above.y; ++y)
        {
            int i = y / 5;
            int j = x / 5;            
            int parket_num = (i * 4 + j) * 5;
            parket_num += ((i + j) % 2 == 0 ? y % 5 : x % 5);            
            ++count_map[parket_num];
        }
    }
    typedef std::multiset<int>  T_multiset;
    T_multiset  multiset;
    for(T_count_map::const_iterator it = count_map.begin(); 
        it != count_map.end(); ++it)
    {    
        multiset.insert(it->second);              
    }
    std::cout << "В заданной области содержится прямоугольников:"
              << std::endl; 
    for(int i = 1; i <= 5; ++i)
    {
        std::cout << "размером 1 x "
                  << i 
                  << ": "
                  << multiset.count(i)
                  << " штук;"
                  << std::endl;
    }
    std::cout << std::endl;
}
//-----------------------------------------------------------------------------
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout << std::endl
                  << std::endl
                  << "Введите координаты левой нижней точки области паркета:"
                  << std::endl;
 
        T_point  left_below;
        std::cout << "X = ";
        std::cin >> left_below.x;
        std::cout << "Y = ";
        std::cin >> left_below.y;
 
        std::cout << std::endl
                  << "Введите координаты правой верхней точки области паркета:"
                  << std::endl;
 
        T_point  right_above;
        std::cout << "X = ";
        std::cin >> right_above.x;
        std::cout << "Y = ";
        std::cin >> right_above.y;
        
        count_parket(left_below, right_above);
    }   
    return 0;
}
1
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
02.09.2010, 09:32 #6
Цитата Сообщение от Mayonez Посмотреть сообщение
как различать
А зачем различать?
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
02.09.2010, 09:34 #7
Для бесконечного паркета:
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
//-----------------------------------------------------------------------------
typedef std::string           T_str;
typedef std::map<T_str, int>  T_count_parquet_cells;
typedef std::multiset<int>    T_rectangles_sizes;
 
const int PARQUET_BLOCK_SIZE = 5;
//-----------------------------------------------------------------------------
T_str  int_to_str(int n)
{
    std::ostringstream  sout;
    sout << n;
    return sout.str();
}
//-----------------------------------------------------------------------------
T_str  parquet_coords_to_str(int x, int y)
{    
    int i = y / PARQUET_BLOCK_SIZE;
    int j = x / PARQUET_BLOCK_SIZE;                
    int n = ((i + j) % 2 == 0 ? y : x ) % PARQUET_BLOCK_SIZE;
    return int_to_str(i) + " " + int_to_str(j) + " " + int_to_str(n);
}
//-----------------------------------------------------------------------------
struct T_point
{
    int x;
    int y;
};
//-----------------------------------------------------------------------------
void count_rectangles(T_point  left_below, T_point  right_above)
{
    T_count_parquet_cells  count_parquet_cells;
    for(int x = left_below.x; x < right_above.x; ++x)
    {
        for(int y = left_below.y; y < right_above.y; ++y)
        {
            ++count_parquet_cells[parquet_coords_to_str(x, y)];
        }
    }
    
    T_rectangles_sizes  rectangles_sizes;
    for(T_count_parquet_cells::const_iterator it = count_parquet_cells.begin(); 
        it != count_parquet_cells.end(); ++it)
    {    
        rectangles_sizes.insert(it->second);              
    }
    std::cout << std::endl
              << "В заданной области содержится прямоугольников:"
              << std::endl; 
    for(int i = 1; i <= PARQUET_BLOCK_SIZE; ++i)
    {
        std::cout << "размером 1 x "
                  << i 
                  << ": "
                  << rectangles_sizes.count(i)                  
                  << " шт."
                  << std::endl;
    }
    std::cout << std::endl;
}
//-----------------------------------------------------------------------------
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout << std::endl
                  << std::endl
                  << "Введите координаты левой нижней точки области паркета:"
                  << std::endl;
 
        T_point  left_below;
        std::cout << "X = ";
        std::cin >> left_below.x;
        std::cout << "Y = ";
        std::cin >> left_below.y;
 
        std::cout << std::endl
                  << "Введите координаты правой верхней точки области паркета:"
                  << std::endl;
 
        T_point  right_above;
        do
        {
            std::cout << "X = ";
            std::cin >> right_above.x;        
        }while(right_above.x < left_below.x);
 
        do
        {
            std::cout << "Y = ";
            std::cin >> right_above.y;        
        }while(right_above.y < left_below.y);
        
        count_rectangles(left_below, right_above);
    }   
    return 0;
}
1
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
07.09.2010, 19:18  [ТС] #8
наконец разобрался
1) считываем кординаты
2) для каждой клетки закрашеной области находим три числа i j n (для клеток, которые принадлежат одному прямоугольнику 1х5 эти три числа будут одинаковые)
3) считаем сколько есть уникальных комбинаций с помощью асоциативного контейнера
4) кидаем всё в multiset чтобы легче было посчитать сколько прямоугольников 1х2, х3, х4, х5
конец
всё правильно понял???

и если уже проводить проверку входных даных, то нужно проверить left_below.y=>0 and left_below.x=>0
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.09.2010, 19:53 #9
Цитата Сообщение от Mayonez Посмотреть сообщение
...наконец разобрался
всё правильно понял???
Ну да.

Цитата Сообщение от Mayonez Посмотреть сообщение
и если уже проводить проверку входных даных, то нужно проверить left_below.y=>0 and left_below.x=>0
Да у меня работает для паркета, заполняющего всю плоскость. А проверка для того чтобы левая нижняя точка области была действительно левее и ниже правой верхней.
0
Шляпа
5 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 64
02.03.2013, 20:55 #10
Ребят, а как сост. прогу к следующ. задаче, тоже про паркетчик. Т.е. надо написать прогр. которая кладет паркет на пуст. место в помещ.. Помещение и припятствия(стены) задается массивом, из 0 и 1 соотв.. Место нахождения паркетчика зададим, например, цифрой 5. а место уклад. паркета будем обозн. буквой-п.
Например, дан массив:
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 1 0 0 1 0 1
1 1 1 5 1 1 1

Должен вывести:

1 1 1 1 1 1 1
1 п п п п п1
1 1 п п 1 п 1
1 1 1 5 1 1 1

Добавлено через 20 часов 21 минуту
Кстати, нашел похожий алгоритм от игры "Жучка".http://buglab.ru/index.asp?main=game
Вот его java-код:
Java
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
function MakeMove(){
   var kx2,ky2,down,right,up,left,cur,l,nn=speed;
   if(!go) return;
   do{
    nn*=2
    if((kx==28)&&(ky==6)){
        return
    }else{
      kx2=kx; ky2=ky; n++
      down=M[ky+1][kx]
      right=M[ky][kx+1]
      up=M[ky-1][kx]
      left=M[ky][kx-1]
      if(dir==0) cur=down
      if(dir==1) cur=right
      if(dir==2) cur=up
      if(dir==3) cur=left
      if((cur<=down)&&(cur<=right)&&(cur<=up)&&(cur<=left)){
        if(dir==0) ky2++
        if(dir==1) kx2++
        if(dir==2) ky2--
        if(dir==3) kx2--
      }else
      if((down<=right)&&(down<=up)&&(down<=left)){ky2++;dir=0}else
      if((right<=down)&&(right<=up)&&(right<=left)){kx2++;dir=1}else
      if((up<=right)&&(up<=down)&&(up<=left)){ky2--;dir=2}else
      if((left<=right)&&(left<=down)&&(left<=up)){kx2--;dir=3}
      M[ky][kx]++
      kx=kx2;ky=ky2
    }
   }while(nn<2)
  }
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2013, 20:55
Привет! Вот еще темы с ответами:

Поиск максимального паросочетания в задаче "Испорченный паркет" - Алгоритмы
Привет всем! Прошу помощи. Есть задача &quot;Испорченный паркет&quot;. Условие задачи следующее: Пол в некоторой комнате размером M ×N...

Решить задачу "Паркет". Найти количество способов замостить эту площадь фигурами - C#
Здравствуйте! Нужна помощь, нужно решить олимпиадную задачку по динамическому программированию по профилю на С#. Обшарил весь нет, нашел...


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

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
02.03.2013, 20:55
Ответ Создать тему
Опции темы

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