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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Daymon28
0 / 0 / 0
Регистрация: 23.10.2013
Сообщений: 11
#1

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

04.12.2013, 15:23. Просмотров 1912. Ответов 7
Метки нет (Все метки)

Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?
Пример. Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.

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

Создать программу (Подсчитать, на сколько кусков распадется оставшаяся часть листа). - C++
Из листа клетчатой бумаги размером M*K клеток удалили некоторые клетки. Подсчитать, на сколько кусков распадется оставшаяся часть листа. ...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) - C++
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На...

из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа? - C++
условие:из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа? Первая строка...

Из листа клетчатой бумаги размером M умножить N клеток удалили некоторые клетки - C++
Из листа клетчатой бумаги размером m * N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Пример....

Из листа клетчатой бумаги размером М*Н клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? - Turbo Pascal
Срочно нужна помощь в выполнении данной задачи, т.к. в Паскале я полный 0. кому не сложно и есть время - выручите. Буду очень признателен

На сколько кусков можно порезать ленту А, если она режется на В, В+0.5, В+1 и тд - Turbo Pascal
Помогите, пожалуйста, решить задачку! С меня огромное спасибо и виртуальная шоколадка)) Из ленты длиной А вырезают куски В, В+0.5,...

7
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");
}
1
xtorne21st
интересующийся
304 / 275 / 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();
}
1
Daymon28
0 / 0 / 0
Регистрация: 23.10.2013
Сообщений: 11
05.12.2013, 00:14  [ТС] #4
спасибо за помощь, но мне нужно именно при помощи стека реализовать данную программу!
0
xtorne21st
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
05.12.2013, 01:45 #5
Цитата Сообщение от Daymon28 Посмотреть сообщение
В нашем алгоритме мы будем находить первую клетку со значением 0, помечаем её определённым образом, а потом находим и помечаем клетки, имеющие общую сторону с найденной клеткой и к тому же со значением 0. Потом находим и помечаем «нулевых» соседей последних найденных клеток и т.д.
Мне вот интересно, как вы это собираетесь организовать без рекурсии?
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
05.12.2013, 01:55 #6
Зачем всё это тут мутите? Обычный BFS заюзать тут(он через очередь пишется), и задача решена
0
xtorne21st
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
05.12.2013, 13:05 #7
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Зачем всё это тут мутите? Обычный BFS заюзать тут(он через очередь пишется), и задача решена
Автор как раз знает какой алгоритм можно использовать и наверняка знает про BFS. Он попросил решить задачу. Мне показалось проще использовать рекурсию. Если вам кажется проще (или просто лучше) использовать BFS, - welcome! Всё в ваших руках
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 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);
}
0
05.12.2013, 18:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2013, 18:24
Привет! Вот еще темы с ответами:

Есть псд, как мне вырезать с него картинки? - HTML, CSS
Есть псд, как мне вырезать с него картинки? Простые квадратики! Подскажите если можете.

Работа со строками. Дано слово. Удалить из него букву О, если такая есть. Удалить из него последнюю букву Л, если такая есть - Turbo Pascal
Привет! Нужна помощь по задачке по паскалю. Пожалуйста помогите! Задание: Дано слово. Удалить из него букву О, если такая есть....

Есть последовательность X1, ., X50. Узнать, есть ли среди них нулевые элементы, и если есть, то сколько - Pascal ABC
Есть последовательность X1, ..., X50. Узнать, есть ли среди них нулевые элементы, и если есть, то сколько.(масив)

Как сделать, чтобы с активного листа некоторые ячейки копировались в один лист, а некоторые - в другой? - VBA
задача. есть таблица в которой 4 столбца. эти четыре столбца должны с капировался так. Первый столбец в лист1, второй в лист два,...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru