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

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

Восстановить пароль Регистрация
 
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
12.07.2015, 16:38     Найти количество островов из единиц #1
Здравствуйте, есть задачка.
Задача Острова
Каждый элемент квадратной матрицы размеренности 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;
                }
          }
    }
}



Код данной программы реализован без графов. А мне нужно используя поиск в глубину реализовывать данный алгоритм. Есть идеи?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,692
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");
}
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
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;
}
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
дело в компиляторе? если у вас все работало? подскажите в какой среде вы работаете?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,692
13.07.2015, 03:56     Найти количество островов из единиц #5
Цитата Сообщение от xDanceRx Посмотреть сообщение
дело в компиляторе? если у вас все работало?
Да, у вас новый стандарт не поддерживает, auto не воспринимает. Можно просто явно тип указать.
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 09:57  [ТС]     Найти количество островов из единиц #6
а какой нужно использовать компилятор, что бы поддерживал auto?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,692
13.07.2015, 10:05     Найти количество островов из единиц #7
Цитата Сообщение от xDanceRx Посмотреть сообщение
а какой нужно использовать компилятор, что бы поддерживал auto?
Ну, все более-менее свежие поддерживают.
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 11:50  [ТС]     Найти количество островов из единиц #8
dev с++ должен все поддерживать, а точней его базовый компилятор. Погуглив узнал, что есть не мало вариаций, компилятора. Будь те добры, скажите свою среду и компилятор.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,692
13.07.2015, 11:53     Найти количество островов из единиц #9
У меня студия.
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
13.07.2015, 12:00  [ТС]     Найти количество островов из единиц #10
понял, скачаю, протестирую, спасибо.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
13.07.2015, 13:40     Найти количество островов из единиц #11
xDanceRx, а не легче сначала поправить тип итератора в программе и иметь сразу нормальную рабочую программу, а отправляться переустанавливать компилятор лишь потом?
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
14.07.2015, 09:14  [ТС]     Найти количество островов из единиц #12
Легче, если знаешь какой тип должен быть, думаю разбираться с кодом лучше тогда, когда он работает. Но если вам не составит труда " поправить тип итератора в программе" будет просто замечательно.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
15.07.2015, 09:49     Найти количество островов из единиц #13
Надо найти "острова" на квадратной матрице
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
15.07.2015, 11:29  [ТС]     Найти количество островов из единиц #14
Мне нужно осуществить реализацию с помощью графа, поэтому вариант выше - не подходит. Спасибо.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16843 / 5264 / 323
Регистрация: 30.03.2009
Сообщений: 14,159
Записей в блоге: 26
15.07.2015, 11:40     Найти количество островов из единиц #15
Цитата Сообщение от xDanceRx Посмотреть сообщение
Мне нужно осуществить реализацию с помощью графа
Насколько я понял, нужно именно через поиск в глубину. А в графе этот поиск, в матрице, или где-то ещё - дело десятое. Матрица всегда может рассматриваться как отображение графа. Удаление острова в моём примере делается поиском в глубину
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2015, 10:55     Найти количество островов из единиц
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33
28.07.2015, 10:55  [ТС]     Найти количество островов из единиц #16
Доброе времени суток! Я новичок в программировании. Мне не понятен вот этот код. Написан он очень уж умно. А мне нужен примитивный, просто код, что бы его можно было легко читать. А этот код даже "загуглив" практически каждую строчку, требует практики, что бы его понять. Может быт, кто- нибудь смог бы его переписать более просто? на базовом уровне?

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
#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");
}
этот код к такому заданию, только я не понял, в этом алгоритме есть обход в глубину или нету?

Задача Острова
Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо
единице. Найдите количество «островов», образованных единицами. Под «островом»
понимается группа единиц (либо одна единица), со всех сторон окруженная нулями
(или краями матрицы). Единицы относятся к одному «острову», если из одной из них
можно перейти к другой «наступая» на единицы, расположенные в соседних клетках.
Соседними являются клетки, граничащие по горизонтали или вертикали.
Уточним, что одна единица тоже считается островом. Также предлагаю считывать
матрицу из файла.
Входные данные
В первой строке файла INPUT.TXT записано натуральное число N не больше 100 -
размер квадратной матрицы. В следующих N строках задаются элементы матрицы
через пробел.
Выходные данные
В файл OUTPUT.TXT выведите единственное число - количество островов.
Пример
INPUT.TXT
4

OUTPUT.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

Решение задачи
Итак, это классическая задача на поиск в глубину графа. Понятно, что надо
обходить матрицу и каким-то образом вычислять количество островов. Вариант решения такой: после того, как мы попадаем на остров, надо это зафиксировать
увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и
тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить
всем клеткам острова значение ноль.
Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения
островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить"
за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст
нам возможность окружить искомый массив размеромN x N нулями.
Yandex
Объявления
28.07.2015, 10:55     Найти количество островов из единиц
Ответ Создать тему
Опции темы

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