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

Найти количество островов из единиц - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Создать консольное приложение на С/С++ для обработки и печати текста http://www.cyberforum.ru/cpp-beginners/thread1497655.html
Создать приложение которое бы -обрабатывала текст -печатала весь текст -печать файла ***печать всех слов содержащих букву А -печать первого слова каждой строки Помогите пожалуйста, буду очень признательна!
C++ Не получается создать класс Account из книги Дейтелов Задача: Создайте класс с именем Account, которым мог бы воспользоваться банк для представления банковских счетов своих клиентов. Ваш класс должен иметь один элемент данных типа int для представления банковского баланса.Класс должен предусматривать конструктор для инициализации элемента данных. Конструктор должен подтверждать значение начального баланса и гарантировать, что оно больше или... http://www.cyberforum.ru/cpp-beginners/thread1497620.html
C++ Напечатать слова последовательности, которые отличны от последнего слова и удовлетворяют заданным свойствам
Дана последовательность, содержащая до 5 слов, в каждом из которых до 5 строчных латинских букв; между соседними словами — не менее одного пробела, за последним словом точка. Напечатать те слова последовательности, которые отличны от последнего слова и удовлетворяют следующему свойству: 1) каждая буква входит в слово не менее двух раз; 2) в слове гласные буквы (a, e, i, o, u)...
Какая скорость ввода gets? C++
Собственно какая скорость ввода gets? К примеру у scanf'a 2 секунды, а gets'a?
C++ Нужно написать бинарное дерево и выполнить ряд заданий http://www.cyberforum.ru/cpp-beginners/thread1497597.html
написать бинарное дерево на задания: 1. Реализуйте программу, в которой выполняются все основные операции с бинарным деревом. 2. Найдите количество четных элементов бинарного дерева. Укажите эти элементы и их уровни. 3. Найдите сумму элементов сбалансированного дерева, находящихся на уровне k. 4. Оператор мобильной связи организовал базу данных абонентов, содержащую сведения о...
C++ Ошибка в коде (Ошибка сегментирования (core dumped) Добрый день. Подскажите пожалуйста, где ошибка в коде? char ch; string s; while ((ch = cin.get()) != '0' ) { подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,650
12.07.2015, 19:14     Найти количество островов из единиц
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
/////////////////////////////////////////////////////////////////////////////////////////
//Задача Острова
/*
Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо
единице. Найдите количество «островов», образованных единицами. Под «островом»
понимается группа единиц (либо одна единица), со всех сторон окруженная нулями
(или краями матрицы). Единицы относятся к одному «острову», если из одной из них
можно перейти к другой «наступая» на единицы, расположенные в соседних клетках.
Соседними являются клетки, граничащие по горизонтали или вертикали.
Уточним, что одна единица тоже считается островом. Также предлагаю считывать
матрицу из файла.
 
ВХОДНЫЕ ДАННЫЕ
В первой строке файла INPUT.TXT записано натуральное число N не больше 100 -
размер квадратной матрицы. В следующих N строках задаются элементы матрицы
через пробел.
 
ВЫХОДНЫЕ ДАННЫЕ
В файл OUTPUT.TXT выведите единственное число - количество островов.
Пример
INPUT.TXT
5
1 0 1 1 1
0 0 0 0 0
1 1 1 0 1
0 1 0 0 1
0 0 0 1 1
 
OUTPUT.TXT
4
Решение задачи
Итак, это классическая задача на поиск в глубину графа.
*/
/////////////////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <fstream>
#include <iostream>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef std::pair   < int,  int     >   T_cell;
typedef std::set    < T_cell        >   T_cells;
/////////////////////////////////////////////////////////////////////////////////////////
void    go_to_cell_with_cells_and_visited_cells
    (
        T_cell                  cell,
        T_cells     const   &   cells,
        T_cells             &   visited_cells
    )
{
    visited_cells.insert( cell );
 
    for (
            auto
            adj_cell_it     =   cells.begin     ();
            adj_cell_it     !=  cells.end       ();
            ++adj_cell_it
        )
    {
        if  (
                    visited_cells.count( *adj_cell_it )     ==  0
 
                &&  (
                                abs( cell.first     -   adj_cell_it->first      )
                            +   abs( cell.second    -   adj_cell_it->second     )
                        ==  1
                    )
            )
        {
            go_to_cell_with_cells_and_visited_cells
                (
                    *adj_cell_it,
                    cells,
                    visited_cells
                );
        }
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
int     get_islands_count_of( T_cells   const   &   cells )
{
    int         res_count   =   0;
    T_cells     visited_cells;
 
    for (
            auto
            cell_it     =   cells.begin     ();
            cell_it     !=  cells.end       ();
            ++cell_it
        )
    {
        if  (
                visited_cells.count( *cell_it )     ==  0
            )
        {
            ++res_count;
 
            go_to_cell_with_cells_and_visited_cells
                (
                    *cell_it,
                    cells,
                    visited_cells
                );
        }
    }//for
 
    return  res_count;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    const   T_str   INPUT_FILENAME      =   "input.txt";
    const   T_str   OUTPUT_FILENAME     =   "output.txt";
 
    std::ifstream   ifile( INPUT_FILENAME );
    T_cells     cells;
 
    if( !ifile )
    {
        std::cout   <<  "Невозможно прочитать данные из файла."
                    <<  std::endl;
    }
    else
    {
        int     matr_dim    =   0;
        ifile   >>  matr_dim;
 
        for( int  i = 0; i < matr_dim; ++i )
        {
            for( int  j = 0; j < matr_dim; ++j )
            {
                int     cell_val    =   0;
                ifile   >>  cell_val;
 
                if( cell_val )
                {
                    cells.insert    (
                                        T_cell( i, j )
                                    );
                }
            }//for
        }//for
 
        std::ofstream   ofile( OUTPUT_FILENAME );
        ofile   <<  get_islands_count_of( cells );
    }//else
 
    system("pause");
}
 
Текущее время: 16:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru