Форум программистов, компьютерный форум 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. программка легкая, но я повторюсь, что я занимаюсь самостоятельным изучением.....помогите... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
30.07.2011, 12:08     [Матрица] Круг или квадрат?
Цитата Сообщение от 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;
}
 
Текущее время: 04:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru