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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.63
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.07.2011, 20:54     [Матрица] Круг или квадрат? #1
Доброго времени суток.
Условие тут.
Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения.
Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 20:54     [Матрица] Круг или квадрат?
Посмотрите здесь:

Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг) C++
C++ Построить классы для описания плоских фигур:круг,квадрат,прямоугольник
Квадрат,круг,стрелка,ромб C++
C++ Известны площади круга и квадрата. Определить: а)местится ли круг в квадрате б)уместится ли квадрат в круге
Определить, когда круг и квадрат касаются (пересекаются) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:07  [ТС]     [Матрица] Круг или квадрат? #21
Цитата Сообщение от grizlik78 Посмотреть сообщение
Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
Каким образом?
Допустим, такой тест
..........
..........
..........
..........
..***.....
..*.*.....
..***.....
..........
..........
..........
Это ведь не может быть квадратом...
Ну а кроме таких случаев у меня вроде все предусмотрено.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
30.07.2011, 19:09     [Матрица] Круг или квадрат? #22
Единички, это то, что было стёрто, двойки, это то, что было нарисовано:
..........
..........
..........
.111......
.1**2.....
.1*12.....
..222.....
..........
..........
..........
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:17     [Матрица] Круг или квадрат? #23
Цитата Сообщение от diagon Посмотреть сообщение
Для всех случаев дополнительное условие писать?
Это касается только размера с одной или обеими сторонами равным 3. Если размер N-2 меньше 2 (я предполагаю, что наименьший квадрат имеет размер 2х2), то просто отсекаешь по краям не по 2, а поменьше строчек/столбцов. Т.е. лишь слегка усложняется алгоритм определения внутренней подматрицы.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:18  [ТС]     [Матрица] Круг или квадрат? #24
grizlik78, Но по вашему алгоритму так немного не получиться..
Ведь здесь вообще нельзя построить квадраты, которые были бы минимум на 2 клетки удалены от всех сторон квадрата. Для этого нужна область минимум 4х4, и все случаи рассматривать как-то нерационально.
Deviaphan, спасибо, попробую...
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
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
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:35  [ТС]     [Матрица] Круг или квадрат? #26
Как квадрат из одной клетки состоять может? о_О
Если из четырех, то точка мешает такие квадраты сделать.
Но вообще таких тестов видимо нету, а я немного не так алгоритм понял(непонятно, на чем основывается такое решение), сейчас переделаю...
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
30.07.2011, 19:36     [Матрица] Круг или квадрат? #27
Цитата Сообщение от diagon Посмотреть сообщение
Как квадрат из одной клетки состоять может? о_О
ну клетка-то квадратная
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:37     [Матрица] Круг или квадрат? #28
Цитата Сообщение от grizlik78 Посмотреть сообщение
ну клетка-то квадратная
Символ "*" больше напоминает круг.)))
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
30.07.2011, 19:39     [Матрица] Круг или квадрат? #29
Цитата Сообщение от Deviaphan Посмотреть сообщение
Символ "*" больше напоминает круг.)))
Снежинку овальную. Но в задаче картинка с квадратными клетками а звёздочки и точки лишь для отличия закрашенных от незакрашенных.
Deviaphan
30.07.2011, 19:41
  #30

Не по теме:

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

grizlik78
30.07.2011, 19:44
  #31

Не по теме:

Точка — круг, но круг — квадрат. Мне заказ, тебе откат! (Все герои вымышленны, все совпадения случайны)

diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 13:21  [ТС]     [Матрица] Круг или квадрат? #32
Блин, эта задача меня убивает...
Вроде как реализовал этот алгоритм.
Цитата Сообщение от 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
#include <iostream>
#define DEBUG
int main(){
    #ifndef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    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;
    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 y = y1; y < y1 + 3; ++y)
        for (int x = x1; x < x1 + 3; ++x)
        {
            bool have_empty_cell = false;
            for (int _x = x, _y = y; 
            !have_empty_cell && _x < x2 && _y < y2;
            ++_x, ++_y)
            {   
                int i, j;
                for (i = y; i <= _y; ++i)
                {
                    for (j = x; j <= _x; ++j)
                        if (matrix[i][j] == '.')
                        {   
                            have_empty_cell = true;
                            if (i != _y && j != x)
                            {
                                --_y;
                                --_x;
                            }
                            break;
                        }
                        if (have_empty_cell)
                            break;
                }
                
                if ( (i != _y || j != _x || !have_empty_cell) && x2 - _x <= 2 && y2 - _y <= 2   )
                            {
                                #ifdef DEBUG
                                std::cout
                                        << std::endl
                                        << x << ' ' << y
                                        << std::endl
                                        << _x << ' ' << _y
                                        << std::endl
                                        << i << ' ' << j 
                                        << std::endl
                                        << std::boolalpha << have_empty_cell
                                        << std::endl;
                                #endif
                                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;
}

Но опять же получаю Wrong Answer на 5 тесте.
И все равно мне непонятно, как этот алгоритм работает.
На чем он вообще основывается?
Еще вот такой тест придумал
Код
....*.....
.....*....
...****...
...***....
...****...
...****...
..........
..........
..........
..........
Нету здесь квадрата.
Однако из точки (4,3) (нумерация с единицы) можно провести недырявый квадрат в точку (6, 5).
Если бы не закрашенная точку сверху, то он мог бы существовать. Но он не существует, а ваш алгоритм говорит об обратном.
Хотя может тут не в алгоритме дело, это уже 3 алгоритм, который на 5 тесте валиться >_>
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
31.07.2011, 13:58     [Матрица] Круг или квадрат? #33
Цитата Сообщение от diagon Посмотреть сообщение
Нету здесь квадрата.
Да есть, есть.
10 10
....2.....
..111*1...
..1****...
..1***1...
..1****...
..1****...
..........
..........
..........
..........

Цитата Сообщение от diagon Посмотреть сообщение
Хотя может тут не в алгоритме дело, это уже 3 алгоритм, который на 5 тесте валиться >_>
В верхней строчке результатов моя реализация моего алгоритма Может я его неправильно реализовал просто?

Добавлено через 23 минуты
diagon, для картинки с одной единственной звёздочкой твоя реализация получает неправильное значение для y2 и выдаёт CIRCLE, хотя одна звёздочка вполне могла остаться от квадрата 3x3
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 14:04  [ТС]     [Матрица] Круг или квадрат? #34
Цитата Сообщение от grizlik78 Посмотреть сообщение
diagon, для картинки с одной единственной звёздочкой твоя реализация получает неправильное значение для y2 и выдаёт CIRCLE, хотя одна звёздочка вполне могла остаться от квадрата 3x3
Убрал там else, все равно WA5 =(
А в какой строке else надо убрать?
В 30й
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
31.07.2011, 14:18     [Матрица] Круг или квадрат? #35
Ну, я только ещё собираюсь разобраться с реализацией. А в какой строке else надо убрать?

Добавлено через 11 минут
В строке 44 должны быть <= вместо меньше, как мне кажется. По-крайней мере для одноклеточной — точно.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 14:21  [ТС]     [Матрица] Круг или квадрат? #36
Цитата Сообщение от grizlik78 Посмотреть сообщение
строке 44 должны быть <= вместо меньше, как мне кажется. По-крайней мере для одноклеточной — точно.
Accepted
Всем спасибо!
P.S. над кодом издеваться все же не буду ибо лень и не умею нормальные макросы для циклов писать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2011, 14:26     [Матрица] Круг или квадрат?
Еще ссылки по теме:

C++ Написать программу, проверяющую, поместится ли круг в квадрат или наоборот.
Вывести на экран круг или квадрат (по выбору пользователя) C++
C++ Известны площади круга и квадрата Уместится ли круг в квадрате или квадрат в круге?

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
31.07.2011, 14:26     [Матрица] Круг или квадрат? #37
Цитата Сообщение от diagon Посмотреть сообщение
И все равно мне непонятно, как этот алгоритм работает.
На чем он вообще основывается?
Алгоритм основан на медитации вот над этой картинкой:
Название: image.asp.gif
Просмотров: 13

Размер: 3.7 Кб
После изменений клетки с цифрами могут стать какими угодно, неизменным остаётся только внутренний квадрат. Задача — найти его, если он есть. Вокруг этого квадрата 2 клетки неопределённости.
Первоначальный выбор 9 точек обусловлен тем, что после изменений координаты x1 и y1 могут отстоять от угла искомого квадрата на 0, 1 и 2 клетки. Ну а расширяя квадрат по диагонали вниз и вправо мы обязательно захватим искомый квадрат хотя бы из одной из 9 начальных клеток (ну может и 1-2 лишних линии).
Yandex
Объявления
31.07.2011, 14:26     [Матрица] Круг или квадрат?
Ответ Создать тему
Опции темы

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