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

На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ расположить элементы строк в порядке убывания. Вставить в каждую строку заданное число http://www.cyberforum.ru/cpp-beginners/thread1028218.html
В массиве А(N,M) расположить элементы строк в порядке убывания. Вставить в каждую строку заданное число р, не нарушая этот
C++ Массивы В массиве А(N,M) расположить строки так, чтобы сначала шли строки, у которых положительных элементов больше, чем отрицательных, затем с одинаковым числом положительных и отрицательных элементов и последними, чтобы шли строки, имеющие положительных элементов меньше, чем отрицательных.:wall: http://www.cyberforum.ru/cpp-beginners/thread1028215.html
Написать функцию, которая вычисляет среднее арифметическое элементов непустого списка C++
вот сам списаок program prog; type pItem = ^Item; Item = record data: integer; next: pItem; end;
Программирование вероятности! C++
Привет! Помогите решить проблему: Пусть есть наборы: категория-мат.ожидание(не вероятность). Например: ручка - (0,18) карандаш - (0,11) циркуль - (0,11) мышка - (0,17) телефон - (-0,66)
C++ Удалить в словах буквы е http://www.cyberforum.ru/cpp-beginners/thread1028168.html
Удалить в словах первое вхождение буквы "е", если такое имеется.
C++ Как описать пустой строковый массив Скажите пожалуйста, как описать пустой строковый массив, если пока неизвестно сколько букв будет в слове, которое запишется в данный массив? подробнее

Показать сообщение отдельно
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
04.12.2013, 19:13     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм.
Вот решение, без очередей, с рекурсией. Проверил с шахматной доской и еще несколько вариантов (в майне векторы инициализируются с помощью initiliazer_list(c++11)). В коде есть функция для рандомных координат, но она не дает k разных координат,она только делает k попыток найти рандомные координаты.

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
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
 
 
 
/*
The function finds random position of cells in the sheet, be aware that k is not a number of cells, but it is a number of tries*/
void  Random(vector<vector<int>>& del,int tries, int m, int n) 
{
    srand(time(NULL));
    for (int i = 0; i < tries; i++)
    {
        del.push_back(vector<int>(2, 0));
        del[i][0] = rand() % m;
        del[i][1] = rand() % n;
    }
}
 
/*
The function deletes cells from sheet . 'del' is array with coordinates of cells that must to be delete
*/
void Delete(vector<vector<int>>& sheet, vector<vector<int>>& del)
{
    for (int i = 0; i < del.size(); i++)
    {
        sheet[del[i][0]][del[i][1]] = -1;
    }
}
 
/*
The function (recursion) paints a cell in sheet[i][j] with colour ,and continues to paint until there is no adjacent cells
*/
void Paint(vector<vector<int>>& sheet,int i,int j, int colour)
{
    sheet[i][j] = colour;
    if ((i - 1) >= 0 && sheet[i-1][j] == 0) Paint(sheet, i - 1, j, colour);
    if ((i + 1)<sheet.size() && sheet[i+1][j] == 0) Paint(sheet, i + 1, j, colour);
    if ((j - 1) >= 0 && sheet[i][j-1] == 0) Paint(sheet, i, j-1, colour);
    if ((j + 1)<sheet[0].size() && sheet[i][j+1] == 0) Paint(sheet, i, j+1, colour);
}
 
/*
Finds a number of shapes
*/
int Find(vector<vector<int>>& sheet)
{
    int colour = 0;
    for (int i = 0; i < sheet.size(); i++)
    {
        for (int j = 0; j < sheet[0].size(); j++)
        {
            if (sheet[i][j] == 0)
            {
                colour++;
                Paint(sheet, i, j, colour);
                
            }
        }
    }
    return colour;
}
void Chess_Table(vector<vector<int>>& sheet)
{
    int f = 0, d = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            f = i * 8 + j;
            if (f%2 == d) sheet[i][j] = -1;
        }
        d = (d == 0) ? 1 : 0;
    }
}
int main()
{
    
    vector<vector<int>> sheet(8, vector<int>(8, 0));
    //_X_
    //XXX
    //_X_
    vector<vector<int>> sheet1 = { { -1, 0, -1 }, { 0, 0, 0 }, { -1, 0, - 1 } };
    //XXX
    //_X_
    //X_X   
    //XXX                                                                               
    vector<vector<int>> sheet2 = { { 0, 0, 0 }, { -1, 0, -1 }, { 0, -1, 0 }, { 0, 0, 0 } };         
    //X_X_X
    //X_X_X
    //X_X_X
    //X_X_X
    //X_X_X
    vector<vector<int>> sheet3 = { { 0, -1, 0, -1, 0 }, { 0, -1, 0, -1, 0 },
    { 0, -1, 0, -1, 0 }, { 0, -1, 0, -1, 0 }, { 0, -1, 0, -1, 0 } };
    
    Chess_Table(sheet);
    cout << Find(sheet1) << endl << Find(sheet2) << endl << Find(sheet3) << endl << Find(sheet)<<endl;
 
 
    
    
    
    system("pause");
}
 
Текущее время: 00:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru