0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
1

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

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

Author24 — интернет-сервис помощи студентам
Здравствуйте, есть задачка.
Задача Острова
Каждый элемент квадратной матрицы размеренности 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.07.2015, 16:38
Ответы с готовыми решениями:

Найти количество «островов»
Данная матрица размерности N N ×, элементами которой являются 0 и 1. Группу единичек, граничащей...

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

В массиве найти количество "островов" из единиц
Помогите перевести с Паскаля на С# или предложите свой вариант решения: Нужно в квадратном...

Найти количество островов в матрице
Здраствуйте, преподаватель дал задание про острова следующего характера. Задана матрица nxm и...

15
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.07.2015, 19:14 2
Лучший ответ Сообщение было отмечено xDanceRx как решение

Решение

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
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
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
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
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
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 03:56 5
Цитата Сообщение от xDanceRx Посмотреть сообщение
дело в компиляторе? если у вас все работало?
Да, у вас новый стандарт не поддерживает, auto не воспринимает. Можно просто явно тип указать.
1
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
13.07.2015, 09:57  [ТС] 6
а какой нужно использовать компилятор, что бы поддерживал auto?
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 10:05 7
Цитата Сообщение от xDanceRx Посмотреть сообщение
а какой нужно использовать компилятор, что бы поддерживал auto?
Ну, все более-менее свежие поддерживают.
1
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
13.07.2015, 11:50  [ТС] 8
dev с++ должен все поддерживать, а точней его базовый компилятор. Погуглив узнал, что есть не мало вариаций, компилятора. Будь те добры, скажите свою среду и компилятор.
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
13.07.2015, 11:53 9
У меня студия.
1
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
13.07.2015, 12:00  [ТС] 10
понял, скачаю, протестирую, спасибо.
0
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
13.07.2015, 13:40 11
xDanceRx, а не легче сначала поправить тип итератора в программе и иметь сразу нормальную рабочую программу, а отправляться переустанавливать компилятор лишь потом?
1
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
14.07.2015, 09:14  [ТС] 12
Легче, если знаешь какой тип должен быть, думаю разбираться с кодом лучше тогда, когда он работает. Но если вам не составит труда " поправить тип итератора в программе" будет просто замечательно.
0
Evg
Эксперт CАвтор FAQ
21276 / 8298 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
15.07.2015, 09:49 13
Надо найти "острова" на квадратной матрице
1
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
15.07.2015, 11:29  [ТС] 14
Мне нужно осуществить реализацию с помощью графа, поэтому вариант выше - не подходит. Спасибо.
0
Evg
Эксперт CАвтор FAQ
21276 / 8298 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
15.07.2015, 11:40 15
Цитата Сообщение от xDanceRx Посмотреть сообщение
Мне нужно осуществить реализацию с помощью графа
Насколько я понял, нужно именно через поиск в глубину. А в графе этот поиск, в матрице, или где-то ещё - дело десятое. Матрица всегда может рассматриваться как отображение графа. Удаление острова в моём примере делается поиском в глубину
0
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
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 нулями.
0
28.07.2015, 10:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.07.2015, 10:55
Помогаю со студенческими работами здесь

Определить по карте количество островов
На карте островного государства Лимония, которая хранится в виде прямоугольной таблицы, нули...

Найти количество единиц
Ребята, помогите пожалуйста кто может! Нужна программа с использованием подпрограммы. Задание:...

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

Определить количество единиц в цифровой записи числа, кроме единиц в младших разрядах
Ребят,помогите,срочно надо! Сам что-то не понимаю( Дано натуральное число N. Определить...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru