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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.63
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

[Матрица] Круг или квадрат? - C++

29.07.2011, 20:54. Просмотров 2469. Ответов 36
Метки нет (Все метки)

Доброго времени суток.
Условие .
Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения.
Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 20:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос [Матрица] Круг или квадрат? (C++):

Вывести на экран круг или квадрат (по выбору пользователя) - C++
Добрый день ! Помогите написать код,чтобы выводился на экрарн круг или квадрат(по выбору пользователя) по идеи нужно реализовать сами...

Написать программу, проверяющую, поместится ли круг в квадрат или наоборот. - C++
3. Заданы круг площади S и квадрат площади Р. Написать программу, проверяющую, поместится ли круг в квадрат или поместится ли квадрат в...

Определить какая из фигур – круг или квадрат - имеет большую площадь - C++
Помогите, составить программу, нужно определить какая из фигур – круг или квадрат - имеет большую площадь. Известно, что сторона...

Известны площади круга и квадрата Уместится ли круг в квадрате или квадрат в круге? - C++
2)Известны площади круга и квадрата. Определить: а) уместится ли круг в квадрат; б) уместится ли квадрат в круге.

Определить, какая из фигур (круг или квадрат) имеет большую площадь и во сколько раз (используя if) - C++
Пусть заданы две фигуры- квадрат и круг. Квадрат задан значением стороны,а круг-радиуса. Определить, какая из фигур имеет большую площадь...

Квадрат,круг,стрелка,ромб - C++
Здравствуйте,помогите написать программу,которая выводит на монитор следующие изображения:Квадрат,круг,стрелка,ромб. Спасибо заранее! :)

36
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2011, 12:08 #16
Цитата Сообщение от grizlik78 Посмотреть сообщение
Не знаю, может я пока и не самый простой алгоритм придумал, но по-крайней мере рабочий.
1. Определяем минимальную прямоугольную область (x1, y1, x2, y2) которая включает в себя все закрашенные клетки.
2. Определяем для проверки 9 клеток с координатами x1 <= x < x+3 и y1 <= y < y+3
3. Для каждой из 9 координат (x, y) находим максимальный квадрат с левым верхним углом в клетке (x, y) и состоящий только из закрашенных клеток.
4. Если хотя бы для одного квадрата правая и нижняя стороны отстоят не дальше чем на 2 клетки от x2 и y2 соответственно, то это мог быть квадрат. Иначе нет.
Да, я вчера тоже к этому алгоритму пришел.
Одна из возможных реализаций:
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>    T_row;
typedef std::vector<T_row>  T_matr;
/////////////////////////////////////////////////////////////////////////////////////////
bool  is_square
    (
        int            rows_total,
        int            cols_total,
        const T_matr&  matr
    )
{
    const int  SQUARE_DIM_MIN  = 3;
    const int  MATR_DIM_MAX    = 1000;
    if(std::min(rows_total, cols_total) < SQUARE_DIM_MIN) return false;
    if(std::max(rows_total, cols_total) > MATR_DIM_MAX  ) return false;
    bool  black_cell_exist = false;
    //Отыскиваем минимальный прямоугольник, содержащий все черные клетки
    //(расширяя область, если встречаем черную клетку).
    int  left_not_white_col    = cols_total;
    int  right_not_white_col   = -1;
 
    int  top_not_white_row     = rows_total;
    int  bottom_not_white_row  = -1;
 
    for(int  row = 0; row < rows_total; ++row)
    {
        for(int  col = 0; col < cols_total; ++col)
        {
            if(matr[row][col])
            {
                black_cell_exist = true;
 
                if(col < left_not_white_col)
                {
                    left_not_white_col = col;    
                }
 
                if(col > right_not_white_col)
                {
                    right_not_white_col = col;    
                }
 
                if(row < top_not_white_row)
                {
                    top_not_white_row = row;    
                }
 
                if(row > bottom_not_white_row)
                {
                    bottom_not_white_row = row;    
                }
            }//if
        }//for(int  col = 0; col < rows_total; ++col)
    }//for(int  row = 0; row < rows_total; ++row)
 
    if(!black_cell_exist) return false;
 
    //Вычисляем размеры полученного прямоугольника.
    int  not_white_W = right_not_white_col  - left_not_white_col + 1;
    int  not_white_H = bottom_not_white_row - top_not_white_row  + 1;
    //Вычисляем минимальную сторону оставшегося квадрата.
    int  remaind_square_W    = std::max(1, not_white_W - 4);
    int  remaind_square_H    = std::max(1, not_white_H - 4);
    int  remaind_square_dim  = std::max(remaind_square_W, remaind_square_H);
 
    //Пробегаемся по левым верхним допустимым вершинам оставшегося квадрата.
    for(int  top_sq_row = top_not_white_row; 
        top_sq_row <= top_not_white_row + 2; 
        ++top_sq_row)
    {
        //Если до нижнего края прямоугольника не больше 2, то:        
        if(bottom_not_white_row - (top_sq_row + remaind_square_dim - 1) <= 2)
        {
            for(int  left_sq_col = left_not_white_col; 
                left_sq_col <= left_not_white_col + 2; 
                ++left_sq_col)
            {
                //Если до правого края прямоугольника не больше 2, то:                
                if(right_not_white_col - (left_sq_col + remaind_square_dim - 1) <= 2)
                {
                    //Проверяем, что все клетки квадрата черные.
                    bool  remaind_square_is_black = true;
                    for(int  rem_sq_row = top_sq_row; 
                        rem_sq_row < top_sq_row + remaind_square_dim;
                        ++ rem_sq_row)
                    {
                        for(int  rem_sq_col = left_sq_col; 
                            rem_sq_col < left_sq_col + remaind_square_dim;
                            ++ rem_sq_col)
                        {
                            if(!matr[rem_sq_row][rem_sq_col])
                            {
                                remaind_square_is_black = false;
                            }
                        }                    
                    }
                    if(remaind_square_is_black)  return true;
                }
            }            
        }
    }
    return  false;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const int  ARR_DIM = 7;
    int  arr[ARR_DIM][ARR_DIM] =
    {
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 1, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 1, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
    };
 
    T_matr  matr(ARR_DIM, T_row(ARR_DIM));
    for(int  i = 0; i < ARR_DIM; ++i)
    {
        for(int  j = 0; j < ARR_DIM; ++j)
        {
            matr[i][j] = arr[i][j];
        }
    }
    std::cout << (is_square(ARR_DIM, ARR_DIM, matr) ? "квадрат" : "круг")
              << std::endl;
}
2
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 18:38  [ТС] #17
Был немного занят...
Попробовал реализовать оба варианта, оба не получилось >_>
Допустим, будет такой тест:
***
*.*
***
Т.к. проверка на дырки не идет по последним двум сторонам, то оба алгоритма считают это квадратом. Собственно, про это и был мой вопрос...
Более коротким кстати оказался вариант от grizlik78, только я немного по другому к нему подошел. Зачем строить кучу квадратов, если интересует только один, одна из вершин которого находиться в правом нижнем углу? Поэтому я строю только один квадрат, одна вершина которого находиться в одной из 9 точек, другая - правый нижний угол предполагаемого квадрата. Если его возможно построить, то смотрю, есть ли в нем дырки, иначе перехожу к следующей точке. Но он получает Wrong Answer на 6 тесте. Да и как он будет работать с вышеприведенным примером я не представляю...
Собственно, код:
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
#include <iostream>
#include <cstdlib> //for abs
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, m;
    std::cin >> n >> m;
    if (n < 3 || m < 3){
        std::cout << "CIRCLE";
        return 0;
    }
    char **matrix = new char* [n];
    for (int i = 0; i < n; ++i)
        matrix[i] = new char [m];
    
    int x1 = n, x2 = -1, y1 = -1, y2 = -1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j){
            std::cin >> matrix[i][j];
            if (matrix[i][j] == '*'){
                if (y1 == -1)
                    y1 = i;
                else
                    y2 = i;
            if (j < x1)
                x1 = j;
            if (j > x2)
                x2 = j;
            }
        }
    
    
    for (int i = y1; i < y1 + 3; ++i)
        for (int j = x1; j < x1 + 3; ++j){
            bool have_whole_cell = false;
            if (abs(i - j) != abs(x2 - y2)) //отсечение неквадратов
                continue;
            for (int x = j; x < x2 - 1; ++x)
                for (int y = i; y < y2 - 1; ++y)
                    if (matrix[y][x] == '.')
                        have_whole_cell = true;
            if (!have_whole_cell){
                std::cout << "SQUARE\n";
                goto del;
            }
        }
    std::cout << "CIRCLE\n";                
    del:
    for (int i = 0; i < n; ++i)
        delete[] matrix[i];
    delete[] matrix;
    
    return 0;
}
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 18:50 #18
Цитата Сообщение от diagon Посмотреть сообщение
Т.к. проверка на дырки не идет по последним двум сторонам, то оба алгоритма считают это квадратом. Собственно, про это и был мой вопрос...
Если K равно 3, то все ячейки должны быть заполнены для квадрата. Просто дополни условие.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:00  [ТС] #19
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если K равно 3, то все ячейки должны быть заполнены для квадрата.
А если 3x4/4x3/4x4/etc ? Для всех случаев дополнительное условие писать?
P.S. исправил мелкую опечатку в коде, теперь Wrong Answer уже на 5 тесте(был на 6м) xD
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
30.07.2011, 19:03 #20
Цитата Сообщение от diagon Посмотреть сообщение
Допустим, будет такой тест:
***
*.*
***
Квадратом это не могло являться только из-за ограниченности поля и размера квадрата. Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
К счастью, такого теста там нет (либо ответ SQUARE для него считается правильным, что, конечно, не верно). Обработка граничных условий сильно бы осложнила алгоритм.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:07  [ТС] #21
Цитата Сообщение от grizlik78 Посмотреть сообщение
Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
Каким образом?
Допустим, такой тест
..........
..........
..........
..........
..***.....
..*.*.....
..***.....
..........
..........
..........
Это ведь не может быть квадратом...
Ну а кроме таких случаев у меня вроде все предусмотрено.
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
30.07.2011, 19:09 #22
Единички, это то, что было стёрто, двойки, это то, что было нарисовано:
..........
..........
..........
.111......
.1**2.....
.1*12.....
..222.....
..........
..........
..........
1
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:17 #23
Цитата Сообщение от diagon Посмотреть сообщение
Для всех случаев дополнительное условие писать?
Это касается только размера с одной или обеими сторонами равным 3. Если размер N-2 меньше 2 (я предполагаю, что наименьший квадрат имеет размер 2х2), то просто отсекаешь по краям не по 2, а поменьше строчек/столбцов. Т.е. лишь слегка усложняется алгоритм определения внутренней подматрицы.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:18  [ТС] #24
grizlik78, Но по вашему алгоритму так немного не получиться..
Ведь здесь вообще нельзя построить квадраты, которые были бы минимум на 2 клетки удалены от всех сторон квадрата. Для этого нужна область минимум 4х4, и все случаи рассматривать как-то нерационально.
Deviaphan, спасибо, попробую...
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
30.07.2011, 19:24 #25
diagon, в каком смысле не получится? Достаточно чтобы хоть один квадрат был не дальше 2 клеток всего от 2 сторон: правой и нижней. Здесь же таких квадратов целых 8, все из одной клетки состоящие.
Код
/tmp $ g++ sqrcirc.cpp && cat input.txt && ./a.out && cat output.txt 
10 10
..........
..........
..........
..........
..***.....
..*.*.....
..***.....
..........
..........
..........
SQUARE
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:35  [ТС] #26
Как квадрат из одной клетки состоять может? о_О
Если из четырех, то точка мешает такие квадраты сделать.
Но вообще таких тестов видимо нету, а я немного не так алгоритм понял(непонятно, на чем основывается такое решение), сейчас переделаю...
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
30.07.2011, 19:36 #27
Цитата Сообщение от diagon Посмотреть сообщение
Как квадрат из одной клетки состоять может? о_О
ну клетка-то квадратная
1
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:37 #28
Цитата Сообщение от grizlik78 Посмотреть сообщение
ну клетка-то квадратная
Символ "*" больше напоминает круг.)))
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
30.07.2011, 19:39 #29
Цитата Сообщение от Deviaphan Посмотреть сообщение
Символ "*" больше напоминает круг.)))
Снежинку овальную. Но в задаче картинка с квадратными клетками а звёздочки и точки лишь для отличия закрашенных от незакрашенных.
0
Deviaphan
30.07.2011, 19:41     [Матрица] Круг или квадрат?
  #30

Не по теме:

Холивар 2011!
Точка - КРУГ она или КВАРДАТ?

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 19:41
Привет! Вот еще темы с ответами:

Определить, когда круг и квадрат касаются (пересекаются) - C++
подскажите пожалуйста как определить когда круг и квадрат касаются (пересекаются)

Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг) - C++
Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг). размер и положение я должен выбрать.

Построить классы для описания плоских фигур:круг,квадрат,прямоугольник - C++
Построить классы для описания плоских фигур:круг,квадрат,прямоугольник.Включить методы для определения периметра и площади...

Известны площади круга и квадрата. Определить: а)местится ли круг в квадрате б)уместится ли квадрат в круге - C++
Известны площади круга и квадрата. Определить: а)местится ли круг в квадрате б)уместится ли квадрат в круге /* Заданы площади круга...


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

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

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