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

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

Войти
Регистрация
Восстановить пароль
 
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
#1

Может кому понадобится - C++

07.07.2011, 23:25. Просмотров 374. Ответов 0
Метки нет (Все метки)

Кое-что из динамического программирования...
Задача подсчёта в прямоугольной матрице количества связных областей (областей состоящих из смежных клеток) . В данном случае вводится матрица из нулей и единиц. Будет подсчитываться кол-во областей состоящих из единиц. 0 - пустая клетка.
Например, я ввожу следующую матрицу размеров 3x5 :
0 1 1 0 0
1 1 0 0 1
1 0 1 0 1
В ней кол-во областей из единиц равно трём, т.е ответ 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
#include <iostream>
#include <windows.h>
 
using namespace std;
 
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    
    int n,m,k=0,In_S=0,In_E=0,i1=0,j1=0;
    int FIFO[100][1];
    int mas[100][100]={};
    cout<<"Введите размеры матрицы(в одной строке через пробел)"<<endl;
    cin>>m>>n;
    cout<<"Введите матрицу из нулей и единиц"<<endl;
    for (int i = 1;i<=m;i++)
    {
        for (int j = 1 ;j<=n;j++)
        {
            cin>>mas[i][j];
        }
    }
    
for (int i = 1;i<=m;i++)
    {
        for (int j = 1 ;j<=n;j++)
        {
            if (mas[i][j]==1)
        {
            k++;
            In_S=0;
            In_E=0;
            FIFO[0][0]=i;
            FIFO[0][1]=j;
            mas[i][j]=2;    
            while (In_S<=In_E)
            { 
                i1 = FIFO[In_S][0];
                j1 = FIFO[In_S++][1];
 
                if (mas[i1+1][j1]==1)
                {
                    FIFO[++In_E][0]=i1+1;
                    FIFO[In_E][1]=j1;
                    mas[i1+1][j1]=2;
                }
 
                if (mas[i1-1][j1]==1)
                {
                    FIFO[++In_E][0]=i1-1;
                    FIFO[In_E][1]=j1;
                    mas[i1-1][j1]=2;
                }
                if (mas[i1][j1+1]==1)
                {
                    FIFO[++In_E][0]=i1;
                    FIFO[In_E][1]=j1+1;
                    mas[i1][j1+1]=2;
                }
                if (mas[i1][j1-1]==1)
                {
                    FIFO[++In_E][0]=i1;
                    FIFO[In_E][1]=j1-1;
                    mas[i1][j1-1]=2;
                }
            }
            }
        }
    }
            
    cout<<"Количество связных областей:  "<<k<<endl;
    system("Pause");
    return 0;
}
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2011, 23:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Может кому понадобится (C++):

Файловый менеджер в консоли (может кому пригодится исходник) - C++
Может у кого то случалась необходимость открыть файл под консольную программу? Предлагаю исходники (написанные под Dev-C++ 4.9.9.2)....

Может кому понадобиться Выключение/перезагрузки компа и завершение сеанса - C++
Копался в windows.h искал чего нибудь интересного вот и нашел.... Вообщем функция для выключения перезагрузки и завершения сеанса...

Что делает данный код и зачем такое кому-нибудь может понадобиться? - C++
Я ответил на вопрос,но точной формулировки не нашёл,хотел бы свериться(приложения с ответами нет).Задание: Чёрный ящик.Что делается в...

Сколько времени понадобится экспедиции, чтобы достичь высоты 4200м? - C++
Экспедиция начинает восхождение на Эверест с высоты 3000 м с начальной скоростью 200 м/ч. Известно, что через каждые 100 м скорость подъема...

Если я хочу написать тетрис не в консоле, какой GUI мне понадобится? - C++
Просто я начала рыться в интернетах. Всего пруд пруди, при чем все разные и со своими нюансами. Может подкажете, какая вообще разница между...

Задача. Сколько времени понадобится экспедиции, чтобы достичь высоты 4200 м? - C++
Сама задача: Экспедиция начинает восхождение на Эверест с высоты 3000 м с начальной скоростью 200 м/ч. Известно, что через каждые 100 м...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2011, 23:25
Привет! Вот еще темы с ответами:

Сколько сравнений понадобится в худшем случае, чтобы упорядочить по возрастанию 4 различных числа - C++
Сколько сравнений понадобится в худшем случае, чтобы упорядочить по возрастанию 4 различных числа (поменять местами значения переменных...

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

кому не сложно - C++
вот программа которая находит площадь пересечения прямоугольников #include &quot;stdafx.h&quot; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include...

Кому нужен помощник?? - C++
Аналонично одной из тем хочу работать в этой сфере (то бишь программировать на С и С++). Только у меня к вам предложение. Кому нужен...


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

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

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