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

Найти свободный участок от деревье и построить там домик - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Подключение файлов obj http://www.cyberforum.ru/cpp-beginners/thread1002360.html
Здравствуйте! Мне очень интересно следующее: допустим есть программа, в которой есть 3 файла (1: main.cpp, 2: class.h, 3: class.cpp) мы их откомпилировали и все хорошо... Но через какое-то время необходимо внести изменения в main.cpp, при этом class.cpp и class.h остаются нетронутыми. Так как же скомпилировать отдельно main.cpp подключив class.h, class.cpp в формате obj и чтобы в итоге...
C++ Скачать веб-страницу Всем привет! Подскажите пожалуйста, как можно скачать в string веб-страницу? http://www.cyberforum.ru/cpp-beginners/thread1002357.html
Русский шрифт C++
Всем доброго времени суток! Недавно начал изучать С++ и столкнулся с небольшой проблемой. При выводе консольного окна win 32 вместо русского текста печатаются каракули. Возможно ли это исправить? З.Ы. Использую компилятор MVS 2010.
C++ Не могу разобраться с кодом
Суть состоит в том чтобы составить программу, выводящую на экран расписание экзаменов и зачетов (предмет,вид отчетности,число,преподаватель) вот собственно сам код: -который не работает у меня должным образом, либо выскакивает либо выдает ошибку , может я что то не так сделала... #include <vcl.h> #include <stdio.h> #include <conio.h> #include <iostream.h> #include <iomanip.h> char*...
C++ Используя перегрузку функции ,написать программу определения минимального значения элемента массива разного типа http://www.cyberforum.ru/cpp-beginners/thread1002342.html
Используя перегрузку функции ,написать программу определения минимального значения элемента массива разного типа
C++ Программная реализация покадрового просмотра файла для ОС семейства Unix Напишите код программы по теме: Программная реализация на языке программирования высокого уровня С++ покадрового просмотра файла для операционных систем семейства Unix. подробнее

Показать сообщение отдельно
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
09.11.2013, 11:18     Найти свободный участок от деревье и построить там домик
Реализация программы работы с матрицами;
Квадратный участок земли размеров NxN метров (N=25 - 200) разбит на клетки со стороной 1 м. Клетка занята, если на ней растут деревья, которые рубить нельзя. Найти для строительства дом квадрат максимальной площади, свободной от деревьев.

Вчера помогал делать это задание клиенту, очень понравилась задачка. Решил выложить, может кому пригодится. И может быть кто знает более интересные способы для ее реализации?

1 - есть деревья
0 - нет деревьев
2 - дом построен


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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
#include <stdlib.h> 
#include <ctime> 
 
using namespace std;
 
int const X = 25, Y = 25; // размер поля
 
class Field
{
private:
    // объявляем переменные класса
    int **mas; // указатель на двумерный массив в котором будут наши участки и деревья. 1 - дерево. 0 - свободное пространство
    int startI, startJ; //индексы первой найденной клетки, которая свободна
    int numberLineMax; // максимальное количество клеток в одной строке, которое было найдено
    bool searchFlaf; // если что-то нашли, то переменная будет хранить true
    
public:
    Field() // конструктор по умолчанию, в нем создаем наш массив
    {
        srand(time(0));// без этого рандомные чмсла будут одинаковые 
 
        // при создании объекта инициализируем переменные нашего класса
        startI = startJ = 0;
        numberLineMax = 0;
        searchFlaf = false;
 
        // если матрица не квадратная, то выходим из программы. по заданию было Х на Х
        if(X != Y) exit(0);
 
        // выделячем память под наш массив
        mas = new int *[X];
        for (int i = 0; i < Y; i++) 
            mas[i] = new int [Y];
 
        // и заполняем массив случайными числами от 0 до 1
        for(int i = 0; i<X; i++)
        {
            for(int j = 0; j<Y; j++)
            {
                mas[i][j] = rand()%2; 
            }   
        } 
        
        cout<<"Вывожу на экран участок земли "<<X<<" на "<<Y<<endl<<endl;
        for(int i = 0; i<X; i++)
        {
            for(int j = 0; j<Y; j++)
            {
                cout<<setw(2)<<mas[i][j];
            }
            cout<<endl;
        } 
        cout<<endl;
    }
 
    bool searchArea(int startI, int startJ)
    {
        int i = startI;
        int j = startJ;
        int numberLine = 0; // колличество клеток в линии и колво клеток, на которое надо спуститься, чтобы обнаружить квадрат.
 
        for(i; i<X; i++) // двигается вниз по строкам
        {
            for(j; j<Y; j++) // двигается в право по столбцам
            {
                    if(numberLine <= 1 && (j+1)>=X) return false; // если ничего не нашли и следующего элемента нет, то выходим и сообщаем, что ничего не нашли
                    if(numberLine > 1 && (j+1)>=X) // если что-то нашли и следующего элемента нет, то нужно начать поиск вниз
                    {
                        if(numberLine>numberLineMax) // нам нужно найти максимально возможный квадрат. и если мы нашли кол-во клеток больше чем в прошлый раз, то пытаемся узнать сможем ли мы построить квадрат
                        {
                            if( depthSearchString(numberLine, startI, startJ) ) // вызываем функцию поиска квадратной площади. если вернет тру, значит в этом месте можно будет построить дом
                            {
                                this->startI = startI;
                                this->startJ = startJ;
                                numberLineMax = numberLine; // сохраняем количество найденных клеток
                                return true;
                            } else return false;
                        } else return false;
                    }
                    if( mas[i][j] == 0)
                    {
                        numberLine++; // с каждой найденной ячейкой записываем +1
                    } 
                    else if(mas[i][j] == 1) // если на пути встретили 1, значит закончились пустые клетки. теперь нужно начать поиск в низ
                    {
                        if(numberLine > 1) // если нашли больше чем одну клетку. ведь если найдена только одна клетка, то квадратной площади не получится. надо минимум 2 клетки.
                        {
                            if(numberLine>numberLineMax) // нам нужно найти максимально возможный квадрат. и если мы нашли кол-во клеток больше чем в прошлый раз, то пытаемся узнать сможем ли мы построить квадрат
                            {
                                if( depthSearchString(numberLine, startI, startJ) ) // вызываем функцию поиска квадратной площади. если вернет тру, значит в этом месте можно будет построить дом
                                {
                                    this->startI = startI;
                                    this->startJ = startJ;
                                    numberLineMax = numberLine; // сохраняем количество найденных клеток
                                    return true;
                                }
                                else return false;
                            } else return false;
                        }
                        else return false;
                    }
            }
        }
    }
 
    /*
        Когда программа находит строку, она записывает в переменную numberLine количество ячеек. чтобы сформировать квадрат, 
        нужно сделать поиск и посмотреть, будет ли сформирован там квадрат. 
    */
    bool depthSearchString(int numberLine, int startI, int startJ) 
    {
        int i = startI;
        int j;
        int count = 0; // будет добавлять сюда по одной найденной клеточке
 
        if ( numberLine > (Y - i) ) return false; // проверяем, возможно ли будет сделать квадрат. хватит ли места
 
        for(i; i<X; i++)
        {
            for(j = startJ; j<startJ+numberLine; j++)
            {
                if(mas[i][j] == 0)
                {
                    count++;
                    if( count/numberLine == numberLine) return true; // если разделить количество только что найденных клеток, на количество ранее найденных клеток в одной линии, то мы получим количество ранее найденных клеток в одной линии. и это значит, что можно строить дом))
                }
                else return false;
            }
        }
    }
 
    void search()
    {
        cout<<"Запускается поиск свободного от деревьев участка"<<endl<<endl;
        for(int i = 0; i<X; i++) // двигается вниз по строкам
        {
            for(int j = 0; j<Y; j++) // двигается в право по столбцам
            {
                if(mas[i][j] == 0) // значит мы нашли пустую клеточку и нужно идти дальше по этой линии в право пока не наткнемся на 1 - значит уже растет дерево
                {
                    if(searchArea(i, j))
                    {
                        cout<<"Найден участок, размер "<<numberLineMax<<" на "<<numberLineMax<<endl;
                        cout<<"Начало кординат: ["<<startI<<"]"<<"["<<startJ<<"]"<<endl<<endl;
                        searchFlaf = true;
                    }
                }
            }
        }
        
        if(!searchFlaf) cout<<endl<<"Поиск участка не дал положительных результатов, слишком много ростительности!";
        else 
            {
                cout<<"Оптимальный участок для строительства найден. Дом построен!"<<" 2 - это ваш участок."<<endl<<endl;
                buildHouse(); // строим дом
            }
    }
 
    void buildHouse()
    {
        for(int i=startI; i<startI+numberLineMax; i++)
        {
            for(int j = startJ; j<startJ+numberLineMax; j++)
            {
                if(mas[i][j] == 0)
                {
                    mas[i][j] = 2;
                }
                else
                {
                    cerr<<"\nОй-ей, какаета ошибка!!!\n";
                }
            }
        }
 
        for(int i = 0; i<X; i++)
        {
            for(int j = 0; j<Y; j++)
            {
                cout<<setw(2)<<mas[i][j];
            }
            cout<<endl;
        } 
        cout<<endl;
 
    }
};
 
 
void main()
{
    setlocale(LC_ALL,"RUSSIAN");
 
    Field field; // создаем объект
    field.search(); // выполняем поиск
 
    getch();
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru