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

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

Войти
Регистрация
Восстановить пароль
 
 
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
#1

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

12.07.2015, 16:38. Просмотров 1065. Ответов 15
Метки нет (Все метки)

Здравствуйте, есть задачка.
Задача Острова
Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо
единице. Найдите количество «островов», образованных единицами. Под «островом»
понимается группа единиц (либо одна единица), со всех сторон окруженная нулями
(или краями матрицы). Единицы относятся к одному «острову», если из одной из них
можно перейти к другой «наступая» на единицы, расположенные в соседних клетках.
Соседними являются клетки, граничащие по горизонтали или вертикали.
Уточним, что одна единица тоже считается островом. Также предлагаю считывать
матрицу из файла.
Входные данные
В первой строке файла INPUT.TXT записано натуральное число N не больше 100 -
размер квадратной матрицы. В следующих N строках задаются элементы матрицы
через пробел.
Выходные данные
В файл OUTPUT.TXT выведите единственное число - количество островов.
Пример
INPUT.TX
T
OUTPUT.TX
T
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
4
Решение задачи
Итак, это классическая задача на поиск в глубину графа. Понятно, что надо
обходить матрицу и каким-то образом вычислять количество островов. Вариантрешения такой: после того, как мы попадаем на остров, надо это зафиксировать
увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и
тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить
всем клеткам острова значение ноль.
Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения
островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить"
за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст
нам возможность окружить искомый массив размеромN x N нулями.

вот код

Кликните здесь для просмотра всего текста
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void is_col(int**, int row, int col, const int size);
void is_row(int**, int row, int col, const int size);
void count_island(int**, const int size, int& len);
 
int  main(void) 
{
     int size = 0, r, c;
     FILE* fp = fopen("1.txt", "r"); // открываем файл
     if(! fp)
         exit(1);
     fscanf(fp, "%2d", &size); // считываем sqrt(размер) матрицы
     fgetc(fp);
     if(! size) {
           fclose(fp);
           exit(2);
      }
      // выделяем динамическую память под матрицу
      int** mat  = new int*[size];
      for(r = 0; r < size; r++)
            mat[r] = new int[size];
 
      char  buf[255];
      char* str;
 
      memset(buf, '\0', sizeof(buf));
      for(r = 0; fgets(buf, sizeof(buf), fp); r++) 
{ // считыаем матрицу из файла
               for(c = 0, str = strtok(buf, " "); str; str = strtok(NULL, " "), c++)
                     mat[r][c] = atoi(str);
      }
      fclose(fp);
 
      int length = 0;
      count_island(mat, size, length);  // подсчитываем острова матрицы
 
     // выводим результат на дисплей и в файл
     fp = fopen("D:\\result.txt", "w+");
     fprintf(fp, "%d", length);
     fclose(fp);
     printf("island count: %d\n", length);
    
     // освобождаем занятую динамическую память
     for(r = 0; r < size; r++) {
            delete[] mat[r];
            mat[r] = NULL;
     }
     delete[] mat;
     mat = NULL;
 
    getchar();
    return 0;
}
 
void is_row(int** mat, int row, int col,  const int size) {
  int r;
  for(r = row + 1; r < size; r++) {
      if(mat[r][col]) {
            is_col(mat, r, col, size);
            mat[r][col] = 0;
      } else
            break;
  } 
  for(r = row - 1; r >= 0; r--) {
      if(mat[r][col]) {
           is_col(mat, r, col, size);
           mat[r][col] = 0;
      } else
          break;
  }
}
 
void is_col(int** mat, int row, int col, const int size) {
  int c;
  for(c = col + 1; c < size; c++) {
       if(mat[row][c]) {
            is_row(mat, row, c, size);
            mat[row][c] = 0;
       } else
            break;
  } 
  for(c = col - 1; c >= 0; c--) {
       if(mat[row][c]) {
           is_row(mat, row, c, size);
           mat[row][c] = 0;
       } else
           break;
  }
}
 
void count_island(int** mat, const int size, int& len) {
    int r, c;
prev:
    for(r = 0; r < size; r++) {
          for(c = 0; c < size; c++) {
               if(mat[r][c]) {
                    is_row(mat, r, c, size);
                    is_col(mat, r, c, size);
                    mat[r][c] = 0;
                    len++;
                    goto prev;
                }
          }
    }
}



Код данной программы реализован без графов. А мне нужно используя поиск в глубину реализовывать данный алгоритм. Есть идеи?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.07.2015, 16:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти количество островов из единиц (C++):

Найти количество островов на море - C++
дана карта в виде массива из 0 и 1, она записана в файле input.txt с таким форматом: в первой строке файла записано 2 числа - кол-во...

Определить по карте количество островов - C++
На карте островного государства Лимония, которая хранится в виде прямоугольной таблицы, нули обозначают море, а единицы -– сушу. Все...

Подсчитать количество единиц в числе, кроме единиц в младших разрядах - C++
Дано натуральное число N. Определить количество единиц в цифровой записи числа, кроме единиц в младших разрядах (Пример: N=81102121, кол-во...

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

Найти количество единиц в числе с 5 по 10 бит - C++
Ввести целое число A и посчитать, сколько единиц в числе с 5 по 10 бит, включая эти биты.

Найти количество квадратов из единиц в двумерном массиве - C++
Добрый день. Я начинающий программист. Решаю задачки и вот столкнулся с такой пробл.: Почему при вводе данных: 1 - кол-во...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
12.07.2015, 19:14 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
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");
}
1
Геомеханик
622 / 429 / 310
Регистрация: 26.06.2015
Сообщений: 968
12.07.2015, 19:45 #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
#include <stdio.h>
#include <malloc.h>
 
typedef struct _stack {
    struct _stack* next;
    int    row, col;
} stack_t;
 
static void stack_push(stack_t** s, int row, int col);
static void stack_pop(stack_t** s);
 
 
//кол-во островов
int count_islands(FILE* _out, FILE* _in){
    int      num, i, j, r, c, r1, c1, d, isn;
    char*    mat, *p;
    stack_t* st;
 
    const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
    
    if(fscanf(_in, "%d", &num) != 1)
        return 0;
 
    mat = (char*)malloc((num*num) * sizeof(char));
    if(mat == NULL)
        return 0;
 
    p = mat;
    for(i = num * num; i > 0; --i){
        if(fscanf(_in, "%1d", &d) != 1){
            free(mat);
            return 0;
        }
        *p++ = (char)d;
    }
    
    //поиск островов
    isn = 0;
    for(i = 0; i < num; ++i){
        for(j = 0; j < num; ++j){
            if(! mat[i*num + j])
                continue;
 
            st = NULL;
            stack_push(&st, i, j);
 
            while(st != NULL){
                r = st->row;
                c = st->col;
                stack_pop(&st);
 
                mat[r*num + c] = 0;
                for(d = 0; d < 4; ++d){
                    r1 = r + dir[d][0];
                    c1 = c + dir[d][1];
                    if((r1 <  0)   || (c1 < 0) ||
                       (r1 >= num) || (c1 >= num))
                       continue;
 
                    if(mat[r1*num + c1])
                        stack_push(&st, r1, c1);
                }
            }
            ++isn;
        }
    }
 
    free(mat);
    fprintf(_out, "count islands: %d", isn);
    return 1;
}
 
 
int main(void){
    FILE* fin  = fopen("input.txt",  "r");
    FILE* fout = fopen("output.txt", "w+");
    count_islands(fout, fin);
    fclose(fout);
    fclose(fin);
 
/*  можно задать с консоли
    printf("Enter N: ");
    count_islands(stdout, stdin);
    fflush(stdin);
*/
    return 0;
}
0
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
12.07.2015, 23:12  [ТС] #4
спасибо за быстрый отклик, решил компильнуть, dev c++ пишет ошибки
строка 23 adj_cell_it = cells.begin (); [Error] 'adj_cell_it' does not name a typeм
строка 24 adj_cell_it != cells.end (); [Error] 'adj_cell_it' was not declared in this scope
дело в компиляторе? если у вас все работало? подскажите в какой среде вы работаете?

Добавлено через 49 минут
Геомеханик, спасибо за быстрый отклик, решил компильнуть, dev c++ пишет ошибки
строка 23 adj_cell_it = cells.begin (); [Error] 'adj_cell_it' does not name a typeм
строка 24 adj_cell_it != cells.end (); [Error] 'adj_cell_it' was not declared in this scope
дело в компиляторе? если у вас все работало? подскажите в какой среде вы работаете?
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 03:56 #5
Цитата Сообщение от xDanceRx Посмотреть сообщение
дело в компиляторе? если у вас все работало?
Да, у вас новый стандарт не поддерживает, auto не воспринимает. Можно просто явно тип указать.
1
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 09:57  [ТС] #6
а какой нужно использовать компилятор, что бы поддерживал auto?
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 10:05 #7
Цитата Сообщение от xDanceRx Посмотреть сообщение
а какой нужно использовать компилятор, что бы поддерживал auto?
Ну, все более-менее свежие поддерживают.
1
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 11:50  [ТС] #8
dev с++ должен все поддерживать, а точней его базовый компилятор. Погуглив узнал, что есть не мало вариаций, компилятора. Будь те добры, скажите свою среду и компилятор.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 11:53 #9
У меня студия.
1
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 12:00  [ТС] #10
понял, скачаю, протестирую, спасибо.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
13.07.2015, 13:40 #11
xDanceRx, а не легче сначала поправить тип итератора в программе и иметь сразу нормальную рабочую программу, а отправляться переустанавливать компилятор лишь потом?
1
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
14.07.2015, 09:14  [ТС] #12
Легче, если знаешь какой тип должен быть, думаю разбираться с кодом лучше тогда, когда он работает. Но если вам не составит труда " поправить тип итератора в программе" будет просто замечательно.
0
Evg
Эксперт CАвтор FAQ
17808 / 6014 / 388
Регистрация: 30.03.2009
Сообщений: 16,527
Записей в блоге: 26
15.07.2015, 09:49 #13
Надо найти "острова" на квадратной матрице
1
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
15.07.2015, 11:29  [ТС] #14
Мне нужно осуществить реализацию с помощью графа, поэтому вариант выше - не подходит. Спасибо.
0
Evg
Эксперт CАвтор FAQ
17808 / 6014 / 388
Регистрация: 30.03.2009
Сообщений: 16,527
Записей в блоге: 26
15.07.2015, 11:40 #15
Цитата Сообщение от xDanceRx Посмотреть сообщение
Мне нужно осуществить реализацию с помощью графа
Насколько я понял, нужно именно через поиск в глубину. А в графе этот поиск, в матрице, или где-то ещё - дело десятое. Матрица всегда может рассматриваться как отображение графа. Удаление острова в моём примере делается поиском в глубину
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.07.2015, 11:40
Привет! Вот еще темы с ответами:

В массиве найти количество "единиц", стоящих на четных местах - C++
Дан массив из 5 элементов. Найти количество &quot;единиц&quot;, стоящих на четных местах.

Дана строка, состоящая из групп нулей и единиц.Найти количество групп с пятью символами - C++
Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Найти количество групп...

В массиве найти количество "единиц" - C++
Дан массив из 5 элементов. Найти количество &quot;единиц&quot;, стоящих на четных местах. Желательно с кодом)) Спасибо!

Подсчитать общее количество цифр и количество единиц в строке - C++
Вводится текст. Среди символов этого текста имеется несколько цифр. Подсчитать общее количество цифр и количество единиц в строке. Если в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.07.2015, 11:40
Ответ Создать тему
Опции темы

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