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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Visual C++ & Hello world http://www.cyberforum.ru/cpp-beginners/thread337362.html
Вот поставил Visual C++ 2005 Пишу: #include "stdafx.h" #include <iostream.h> int _tmain(int argc, _TCHAR* argv) {
C++ Почему тормозит играаа??? Добрый день - решил недавно создать игрушку (третяя на моем счету)... но на этот раз игра не пошаговая - эдакое подобие бомбермена с инвентарем... Можете пожалуйста подсказать по какой причине игра может тормозить ? (Возможно проблема в алгоритме - основная часть которого в мейн функции(это цикл)- пожалуйста обратите внимание) Администрацию сайта просьба не переносить даное сообщение в... http://www.cyberforum.ru/cpp-beginners/thread337343.html
C++ простые функции
Всем приветик!!! Есть код: #include<iostream.h> #include<conio.h> #include<string.h> enum Shape{prizm,parallelepiped,cube,pyramid,cone,cylinder}; class Body {
C++ Построить эйлерову цепь в графе.
Всем доброго времени суток! Помогите пожалуйста или подскажите как сделать следующее. Дали задание по дискретной математике построить эйлерову цепь в графе (нужно реализовать все программе, но вот не знаю с чего начать). Задание следующее: Построить эйлерову цепь в графе. Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе....
C++ MinGW запрет неявного преобразования типов http://www.cyberforum.ru/cpp-beginners/thread337306.html
Существует ли какой то режим у gcc (MinGW) где бы компилятор "ругался" или хотя бы предупреждал о неявном преобразование типов? Причем не важно: int -> double или double -> int
C++ Помогите написать программку - лотерею Я сам только окончил первый курс технаря...учусь отлично...решил, что пока каникулы, заняться изучением C++......как-то он меня увлек....вчера в голову пришла идея, написать программку - лотерею...типа вводишь несколько чисел подряд, программка их перебирает и выводит какое-то число на экран.... P.s. программка легкая, но я повторюсь, что я занимаюсь самостоятельным изучением.....помогите... подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 13:21  [ТС]     [Матрица] Круг или квадрат?
Блин, эта задача меня убивает...
Вроде как реализовал этот алгоритм.
Цитата Сообщение от 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 тесте валиться >_>
 
Текущее время: 03:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru