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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Daymon28
0 / 0 / 0
Регистрация: 23.10.2013
Сообщений: 11
04.12.2013, 15:23     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #1
Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?
Пример. Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.

Добавлено через 1 минуту
К – количество удалённых клеток, (х1; у1), …, (хk; yk) – координаты удалённых клеток.
Для решения данной задачи рассмотрим двумерный массив M x N, где удалённые клетки имеют значение -1, а неудалённые – 0.
В нашем алгоритме мы будем находить первую клетку со значением 0, помечаем её определённым образом, а потом находим и помечаем клетки, имеющие общую сторону с найденной клеткой и к тому же со значением 0. Потом находим и помечаем «нулевых» соседей последних найденных клеток и т.д. Процесс заканчивается, когда никаких новых клеток не удаётся найти. Значит, мы получили единый кусок листа.
Далее выбираем новую начальную клетку и опять повторяем процесс нахождения её «соседей», равных 0.
Алгоритм закончится, когда на «листе» не останется клеток со значением 0.
Для решения задачи будем использовать очередь. В очереди будем хранить вновь помеченные клетки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.12.2013, 15:23     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм.
Посмотрите здесь:

C++ из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа?
C++ Есть объект типа T, но если вместо него подставить вызов функции, возвращающей T, код не компилится, почему?
C++ Нужно написать программу на С/С++ (дано слово. определить сколько в нем различных букв), есть алгоритм
Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) C++
C++ Алгоритм Дейкстры (часть кода есть)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
04.12.2013, 19:13     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #2
Вот решение, без очередей, с рекурсией. Проверил с шахматной доской и еще несколько вариантов (в майне векторы инициализируются с помощью 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");
}
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
04.12.2013, 21:20     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #3
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
#include <iostream> // std::cout and so on.
#include <vector> // for std::vector.
#include <utility> // for std::pair.
 
// 0 - cell enable;
// -1 - cell empty;
// 1.. - number of variant.
 
class Desk
{
public:
    // Init desk.
    Desk(int len, int hei)
        : length(len), height(hei)
    {
        board = new int*[height];
        for (int i = 0; i < height; ++i)
        {
            board[i] = new int[length];
 
            for (int j = 0; j < length; ++j)
            {
                board[i][j] = 0;
            }
        }
    }
 
    // Free resources.
    ~Desk()
    {
        for (int i = 0; i < height; ++i)
        {
            delete board[i];
        }
        delete board;
    }
 
public:
    // Handle desk.
    void handle()
    {
        count = 1;
 
        for (int i = 0; i < height; ++i)
        {
            for (int j = 0; j < length; ++j)
            {
                if (board[i][j] == 0)
                {
                    std::vector<std::pair<int, int> > co;
 
                    check(i,j, co); // write coordinates to storage.
                    confirm(co, count); // save coordinates.
                    ++count;
                }
            }
        }
    }
 
    void showDesk()
    {
        for (int i = 0; i < height; ++i)
        {
            for (int j = 0; j < length; ++j)
            {
                std::cout.width(3);
                std::cout << board[i][j];
            }
            std::cout << "\n";
        }
        std::cout << "\n" << std::endl;
    }
 
    void removeCell(int y, int x)
    {
        board[y][x] = -1;
    }
 
    int countResult() const
    {
        return count;
    }
 
private:
    // Check cell.
    void check(const int y, const int x, std::vector<std::pair<int, int> >& coordinates)
    {
        if (x == length || x == -1 || y == height || y == -1)
        {
            return;
        }
        else if (board[y][x] == -1) // if cell empty..
        {
            return;
        }
 
        // Finding equals coordinates.
        for (size_t i = 0; i < coordinates.size(); ++i)
        {
            if (coordinates[i].first == y && coordinates[i].second == x) // if fined - return.
            {
                return;
            }
        }
 
        std::pair<int, int> p(y, x);
        coordinates.push_back(p); // save current location.
 
        check(y, x+1, coordinates); // move forward.
        check(y, x-1, coordinates); // move backward.
        check(y-1, x, coordinates); // move up.
        check(y+1, x, coordinates); // move down.
    }
 
    void confirm(const std::vector<std::pair<int, int> >& coordinates, int value)
    {
        for (size_t i = 0; i < coordinates.size(); ++i)
        {
            board[coordinates[i].first][coordinates[i].second] = value;
        }
    }
 
private:
    const int length;
    const int height;
    int count;
    int** board;
};
 
int main()
{
    Desk desk(8, 8);
    desk.showDesk();
 
    desk.removeCell(0, 1);
    desk.removeCell(1, 0);
 
    desk.removeCell(0, 6);
    desk.removeCell(1, 7);
 
    desk.removeCell(6, 0);
    desk.removeCell(7, 1);
 
    desk.removeCell(6, 7);
    desk.removeCell(7, 6);
 
    desk.removeCell(4, 3);
    desk.removeCell(3, 2);
    desk.removeCell(2, 3);
    desk.removeCell(2, 4);
    desk.removeCell(3, 5);
    desk.removeCell(4, 4);
 
    desk.handle();
 
    desk.showDesk();
}
Daymon28
0 / 0 / 0
Регистрация: 23.10.2013
Сообщений: 11
05.12.2013, 00:14  [ТС]     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #4
спасибо за помощь, но мне нужно именно при помощи стека реализовать данную программу!
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
05.12.2013, 01:45     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #5
Цитата Сообщение от Daymon28 Посмотреть сообщение
В нашем алгоритме мы будем находить первую клетку со значением 0, помечаем её определённым образом, а потом находим и помечаем клетки, имеющие общую сторону с найденной клеткой и к тому же со значением 0. Потом находим и помечаем «нулевых» соседей последних найденных клеток и т.д.
Мне вот интересно, как вы это собираетесь организовать без рекурсии?
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.12.2013, 01:55     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #6
Зачем всё это тут мутите? Обычный BFS заюзать тут(он через очередь пишется), и задача решена
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
05.12.2013, 13:05     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #7
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Зачем всё это тут мутите? Обычный BFS заюзать тут(он через очередь пишется), и задача решена
Автор как раз знает какой алгоритм можно использовать и наверняка знает про BFS. Он попросил решить задачу. Мне показалось проще использовать рекурсию. Если вам кажется проще (или просто лучше) использовать BFS, - welcome! Всё в ваших руках
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2013, 18:24     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм.
Еще ссылки по теме:

Создать программу (Подсчитать, на сколько кусков распадется оставшаяся часть листа). C++
Какие действия исполняет заданная часть программы? Если есть ошибки исправить их и объяснить исправления C++
C++ C/C++ вырезать часть данных с файла

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.12.2013, 18:24     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. #8
вот алгоритм решения задачи(копирнул из архивов)
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
sport.cpp
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <algorithm>
#include <queue>
#include <vector>
 
 
 
using namespace std;
 
bool arr[101][101];
long long m,n,k,temp_i,temp_j,i,ans=0,j;
queue<pair<long long,long long> > q;
 
void input()
{
    scanf("%I64d%I64d%I64d",&m,&n,&k);
    for(i=0;i<k;++i)
    {
        scanf("%I64d%I64d",&temp_i,&temp_j);
        arr[temp_i][temp_j]=true;
    }
}
 
void process()
{
    do
    {
        long long i1=q.front().first,j1=q.front().second;
        arr[i1][j1]=true;
        if(i1+1<=m && arr[i1+1][j1]==false)
        {
            q.push(make_pair(i1+1,j1));
            arr[i1+1][j1]=true;
        }
        if(i1-1>=1 && arr[i1-1][j1]==false)
        {
            q.push(make_pair(i1-1,j1));
            arr[i1-1][j1]=true;
        }
        if(j1+1<=n && arr[i1][j1+1]==false)
        {
            q.push(make_pair(i1,j1+1));
            arr[i1][j1+1]=true;
        }
        if(j1-1>=1 && arr[i1][j1-1]==false)
        {
            q.push(make_pair(i1,j1-1));
            arr[i1][j1-1]=true;
        }
        q.pop();
    }
    while(!q.empty());
}
 
void answer()
{
    for(i=1;i<=m;++i)
        for(j=1;j<=n;++j)
        {
            if(!arr[i][j])
            {
                q.push(make_pair(i,j));
                process();
                ++ans;
            }
        }
}
 
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    input();
    answer();
    printf("%I64d",ans);
}
Yandex
Объявления
05.12.2013, 18:24     На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм.
Ответ Создать тему
Опции темы

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