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

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

Восстановить пароль Регистрация
 
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
09.11.2013, 11:18     Найти свободный участок от деревье и построить там домик #1
Реализация программы работы с матрицами;
Квадратный участок земли размеров 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2013, 11:18     Найти свободный участок от деревье и построить там домик
Посмотрите здесь:

найти в массиве непрерывный участок из 10 чисел с наибольшим средним значением C++
В чём ошибка.В коде там где коментарий там ошибка поучается. C++
Найти непрерывный участок C++
C++ Найти непрерывный участок из 10 элементов, сумма которых максимальна
Условие:Все нулевые елементы заменить на еденицу!Во второй строке у меня там изменённый масив но там выводит нули одни!Почему? C++
Участок B кода выполняется позже, чем участок A кода, но почему-то B влияет на работоспособность A! Почему? C++
Найти непрерывный участок из 10 элементов, который имеет наибольшее среднее значение элементов C++
C++ Найти непрерывный участок последовательности

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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