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

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

Восстановить пароль Регистрация
 
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
07.07.2011, 23:25     Может кому понадобится #1
Кое-что из динамического программирования...
Задача подсчёта в прямоугольной матрице количества связных областей (областей состоящих из смежных клеток) . В данном случае вводится матрица из нулей и единиц. Будет подсчитываться кол-во областей состоящих из единиц. 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2011, 23:25     Может кому понадобится
Посмотрите здесь:

Кому нужен помощник?? C++
C++ [C++]Что делает данный код и зачем такое кому-нибудь может понадобиться?
C++ Кому легко, сюда
C++ кому не сложно
Может кому понадобиться Выключение/перезагрузки компа и завершение сеанса C++
C++ Задача. Сколько времени понадобится экспедиции, чтобы достичь высоты 4200 м?
C++ Сколько сравнений понадобится в худшем случае, чтобы упорядочить по возрастанию 4 различных числа
C++ Исправьте кому не сложно

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

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

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