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

Надо найти "острова" на квадратной матрице - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.60
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
03.06.2009, 01:26     Надо найти "острова" на квадратной матрице #1
Собственно ниже условие и я вроде все понял, но как это сделать...
Буду очень благодарен за Вашу помощь.
Каждый элемент квадратной матрицы размерности NxN равен нулю либо единице. Найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц, со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2009, 01:26     Надо найти "острова" на квадратной матрице
Посмотрите здесь:

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений C++
Заполнить структуры "Прямоугольник" и "Треугольник" и найти площади и периметры фигур C++
C++ Найти и заменить в строке все символы "а" на "b"
C++ Надо написать программу (игру) "Кости". Где ошибка?
C++ Заданный словарь слов. Найти в нем слова-палиндромы, то есть такие, которые одинаково читаются слева направо и наоборот, например, "АННА", "ШАЛАШ"
C++ Найти номер последней по порядку строки в матрице, содержащей наибольшее количество букв "ш", "щ"
Найти все вхождения в строку последовательности символов "сто" и заменить на "100" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mikutu
26 / 26 / 2
Регистрация: 29.04.2009
Сообщений: 90
03.06.2009, 07:06     Надо найти "острова" на квадратной матрице #2
самое простое что пришло в голову это решение этой задачи с помощью 2 дополнительных матриц: 1-ая матрица имеет следующие состояние ячейки 0 и 1 просто дублируют значения в исходной матрице, да еще 0 значит не обрабатывать эту ячейку она не является частью острова, 2 - кадидат на матрицу у которого обработаны все соседи, 3 - кадидат на матрицу у которого обработаны не все соседи. 2-ая матрица (строкового типа) содержит для единичных элементов имя родителя (начало острова имеет родителя себя)
пример
1 0 0
1 1 1
0 0 0
2-ая матрица имеет вид
0;0 0 0
0;0 0;0 1;1
0 0 0
ну и переменной для определения состояния программы true - в поисках начала острова false - обработка острова
Обрабатываться должны все элементы исходного массива, началом острова может быть только элемент у которого значения исходной и 1-ой матрицы равны 1, а 2-ой - 0.
1-ая матрица вначале представляет собой копию исходной, а у 2-ой все элементы равны 0;
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,352
Записей в блоге: 26
03.06.2009, 09:56     Надо найти "острова" на квадратной матрице #3
Возможно, что мой вариант чем-то совпадает с вариантом mikutu, но его объяснения я затруднился понять. Метод мой заключается в следующем. Ищем первую попавшуюся единицу и запускаем процесс, который удалит остров (содержащий данную единицу) с поля. После удаления острова увеличиваем счётчик и ищем слудующую единицу и т.д. Удалять острова можо на оргинальном массиве, а можно и сделать копию

Рекурсивная процедура удаления выглядит примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[10][10]; // <--- наш массив
 
// Удаление острова, содержащего поле x, y
void
delete_island (int x, y)
{
  // Для внутреннего контроля (чтобы убедиться, что мы всё делаем правильно)
  if (a[x][y] != 1)
    abort ();
 
  // Сразу сотрём данную точку, чтобы повторно сюда не зайти и не зациклиться
  a[x][y] = 0;
 
  // Обходим четырёх соседей данной точки, учитывая границы поля
  // Предполагая, что координаты соседа x1, y1, нужно на каждого
  // соседа запутить код
  if (a[x1][y1] == 1)
    delete_island (x1, y1);
}
mikutu
26 / 26 / 2
Регистрация: 29.04.2009
Сообщений: 90
03.06.2009, 11:05     Надо найти "острова" на квадратной матрице #4
кстати в моем прошлом сообщении закраласт небольшая ошибка вместо
2-ая матрица имеет вид
0;0 0 0
0;0 0;0 1;1
0 0 0
нужно
2-ая матрица имеет вид
0;0 0 0
0;0 1;0 1;1
0 0 0
Трой
кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
C
1
2
3
4
5
6
7
 -
|1|  0   0
         -
|1|  0  |1|
 -   -  
 0  |1   1|
     -   -
(просто что бы пробелы не убирало)
Если я понимаю, то в выше приведенной матрице 2 острова.
Вообще решение Evg вроде более просто, но его нужно реализовать и проверить на трудных примерах например таком
1 1 1 1 1
1 0 1 0 0
1 1 0 0 0
0 0 1 1 0
0 1 1 0 0
всего должно быть 2 острова
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,352
Записей в блоге: 26
03.06.2009, 11:59     Надо найти "острова" на квадратной матрице #5
> но его нужно реализовать и проверить на трудных примерах например

Да с этим примером в теории проходит.
Главна тонкость в том, что при вычислении соседа надо соблюсти порядок. Т.е. "в цикле { вычислил соседа - проверил }", но не "в цикле { вычислил соседей }, в цикле { проверил соседей }"
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
04.06.2009, 14:49  [ТС]     Надо найти "острова" на квадратной матрице #6
Evg и mikutu Спасибо за помощь, но у меня все же не получается написать полный код программы.

кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
Хороший вопрос. Я тоже вчера о нем подучал и сегодня хотел спросить его у преподавателя, но она сегодня не пришла
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
07.06.2009, 05:05  [ТС]     Надо найти "острова" на квадратной матрице #7
up
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,352
Записей в блоге: 26
07.06.2009, 12:00     Надо найти "острова" на квадратной матрице #8
И в чём проблема?
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:32     Надо найти "острова" на квадратной матрице #9
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
07.06.2009, 15:42     Надо найти "острова" на квадратной матрице #10
Цитата Сообщение от Ultrator Посмотреть сообщение
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
не понял, почему их будет ДВА?
будет один.
а в качестве координаты острова - брать левый верхний угол, к примеру.
для однозначной идентификации.
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:44     Надо найти "острова" на квадратной матрице #11
Ой, точно.
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 06:07  [ТС]     Надо найти "острова" на квадратной матрице #12
Patch
Да была такая у нас мысль.
Например вводим NxN, как 3x3 и допустим оператор rnd нам выведет такую матрицу:

000
110
110
с координатами:

x1, y1 =1
x2, y1 =1
x3, y1 =0
x1, y2 =1
x2, y2 =1
x3, y2 =0
x1, y3 =0
x2, y3 =0
x3, y3 =0
Наша програма будет проверять все эти координцаты и нужные нам символы откладывать в отдельный массив. Если углубится то сложней конечно будет, но проблема не в этом. Когда я говорил в первом посте, что все понел, то я имел ввиду, что понел поставленную задачу, но я не могу её написать, не могу написать сам код на С++. Скажите сделай сайт я вам замучу афигенский сайт за короткие сроки, но когда дело доходит до С++ я тут дальше cout и cin нешарю.
Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 07:06     Надо найти "острова" на квадратной матрице #13
если я сделаю так, как считаю нужным, работать будет очень быстро и точно, но препод может не понять...
я 15 лет системы распознавания образов разрабатываю.
это задание - частный случай, и довольно простой.
лучше так: Трой, пиши как сам понимаешь, и как умеешь, а мы доделаем, если что не работает.
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 19:04  [ТС]     Надо найти "острова" на квадратной матрице #14
Patch
Ну когда я говорил, что дальше cout и cin не шарю это была правда

Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 19:54     Надо найти "острова" на квадратной матрице #15
Цитата Сообщение от Трой Посмотреть сообщение
Ну когда я говорил, что дальше cout и cin не шарю это была правда
блин, ты-же писать умеешь?
по русски?
зайди на ядекс и спроси: "массивы в c c++"
узнаешь, как их делать.
и делай себе наздоровье.
я лет 15 назад Assembler и С изучал, так у меня была ОДНА растрепанная книга.
почти все делал методом научного тыка, потому как интернета тогда на 600км вокруг небыло, и спросить было не у кого.
а у вас вся информация под рукой...
так нет, лень-матушка...
ленишся читать и думать - иди в раздел "Заказ программ". с деньгами.
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
09.06.2009, 20:50  [ТС]     Надо найти "острова" на квадратной матрице #16
Patch
Этим заниматься я буду позже, тобиш летом когда время будет, а на данный момент у меня сроки поджимают и сделать эту задачу надо срочно. В то же время денег на счету нету. Даже на балансе трнета -полтора бакса и сижу в кредите.
Не думал, что так сложно будет написать код за так. Алчных и жадных людей стало много. Эх Вы!
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,352
Записей в блоге: 26
09.06.2009, 21:52     Надо найти "острова" на квадратной матрице #17
Цитата Сообщение от Трой Посмотреть сообщение
Не думал, что так сложно будет написать код за так. Алчных и жадных людей стало много. Эх Вы!
А ты не думал о том, что людям твои проблемы мягко говоря до фонара (т.е. проблемы негроф шерифа не е$ут) и что задача в общем-то не простая и надо помудохаться, чтобы её написать и отладить. Или ты считаешь, что народ на форуме тусутеся только для того, чтобы тебе программу написать?

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
#include <stdio.h>
#include <stdlib.h>
 
#define DEBUG 1
 
#define N 6
int a[N][N] =
{
 { 1, 0, 1, 1, 0, 1 },
 { 0, 1, 1, 0, 1, 0 },
 { 1, 0, 1, 0, 1, 1 },
 { 1, 1, 1, 0, 0, 1 },
 { 0, 0, 1, 1, 0, 1 },
 { 1, 1, 0, 1, 1, 0 },
};
 
/* Внутренний контроль */
#define ASSERT(x) \
  if (!(x)) abort ();
 
/* Рекурсивная процедура стирания острова, содержащего точку (x,y) */
static void
delete_island (int x, int y)
{
  int dx[4] = { -1, 0, 1, 0 };
  int dy[4] = { 0, -1, 0, 1 };
  int i, x1, y1;
 
  ASSERT (a[x][y] == 1);
 
  /* Сразу сотрём данную точку, чтобы повторно сюда не зайти
   * и не зациклиться */
  a[x][y] = 0;
 
  /* Обходим четырёх соседей и удаляем их */
  for (i = 0; i < 4; i++)
    {
      /* Координаты соседа */
      x1 = x + dx[i];
      y1 = y + dy[i];
 
      /* Проверяем, что сосед попадает в поле и удаляем */
      if (x1 >= 0 && x1 < N && y1 >= 0 && y1 < N)
        if (a[x1][y1] == 1)
          delete_island (x1, y1);
    }
}
 
static void
print (void)
{
  int i, j;
 
  printf ("--------\n");
 
  for (j = 0; j < N; j++)
    {
      for (i = 0; i < N; i++)
        printf ("%d", a[i][j]);
 
      printf ("\n");
    }
}
 
int
main (void)
{
  int count = 0;
  int i, j;
 
  /* Контроль, что матрицу не перекосило */
  ASSERT (sizeof(a) == (sizeof(int) * N * N));
 
  if (DEBUG)
    print ();
 
  for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
      if (a[i][j] == 1)
        {
          /* Удаляем встретившийся остров */
          delete_island (i, j);
          count++;
 
          if (DEBUG)
            print ();
        }
 
  printf ("Number of islands: %d\n", count);
 
  return 0;
}
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
10.06.2009, 22:52  [ТС]     Надо найти "острова" на квадратной матрице #18
Evg
Огромное, человеческое тебе спасибо!
зы За предыдущий пост извеняюсь, погоречился.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2009, 22:57     Надо найти "острова" на квадратной матрице
Еще ссылки по теме:

Надо ли книгу выбрасывать "в топку" (печь топить) C++
C++ Найти угол одной точки "A" в соотношении к точке "B" в градусах
Нужно найти слова которые встречаются в буквы "a" "z" C++
Может ли MSXML в XML файле найти все вхождения "123" в значениях атрибутов элементов и заменить их на "321"? C++
Программа,где надо убрать эти "::" знаки C++

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,352
Записей в блоге: 26
10.06.2009, 22:57     Надо найти "острова" на квадратной матрице #19
Цитата Сообщение от Трой Посмотреть сообщение
зы За предыдущий пост извеняюсь, погоречился.
С каждым бывает
Yandex
Объявления
10.06.2009, 22:57     Надо найти "острова" на квадратной матрице
Ответ Создать тему
Опции темы

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