Форум программистов, компьютерный форум 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 строчных латинских букв; между соседними словами — не менее одного пробела, за последним словом точка. Напечатать те...
Какая скорость ввода gets? C++
Собственно какая скорость ввода gets? К примеру у scanf'a 2 секунды, а gets'a?
C++ Нужно написать бинарное дерево и выполнить ряд заданий http://www.cyberforum.ru/cpp-beginners/thread1497597.html
написать бинарное дерево на задания: 1. Реализуйте программу, в которой выполняются все основные операции с бинарным деревом. 2. Найдите количество четных элементов бинарного дерева. Укажите эти...
C++ Ошибка в коде (Ошибка сегментирования (core dumped) Добрый день. Подскажите пожалуйста, где ошибка в коде? char ch; string s; while ((ch = cin.get()) != '0' ) { подробнее

Показать сообщение отдельно
xDanceRx
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 33

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

12.07.2015, 16:38. Просмотров 1071. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru