Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.52/21: Рейтинг темы: голосов - 21, средняя оценка - 4.52
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
1

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

03.06.2009, 01:26. Просмотров 3924. Ответов 18
Метки нет (Все метки)

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

Найти номер последней по порядку строки в матрице, содержащей наибольшее количество букв "ш", "щ"
Нужен код к этому условию, пожалуйста. Дана символьная матрица размера 13х18....

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов),...

Вывести на экран фразу "Мне n лет", учитывая что при некоторых значениях n слово "лет" надо заменить на "год"
дано натуральное число n. Вывести на экран фразу "Мне n лет", учитывая что при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года "весна", "лето", "осень", "зима" определить...

После каждой буквы "t" надо вставить буквосочетание "rue"
После каждой буквы "t" надо вставить буквосочетание "rue" помогите,...

18
mikutu
27 / 27 / 10
Регистрация: 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;
0
Evg
Эксперт CАвтор FAQ
19306 / 7161 / 533
Регистрация: 30.03.2009
Сообщений: 20,042
Записей в блоге: 30
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);
}
0
mikutu
27 / 27 / 10
Регистрация: 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 острова
0
Evg
Эксперт CАвтор FAQ
19306 / 7161 / 533
Регистрация: 30.03.2009
Сообщений: 20,042
Записей в блоге: 30
03.06.2009, 11:59 5
> но его нужно реализовать и проверить на трудных примерах например

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

кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
Хороший вопрос. Я тоже вчера о нем подучал и сегодня хотел спросить его у преподавателя, но она сегодня не пришла
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
07.06.2009, 05:05  [ТС] 7
up
0
Evg
Эксперт CАвтор FAQ
19306 / 7161 / 533
Регистрация: 30.03.2009
Сообщений: 20,042
Записей в блоге: 30
07.06.2009, 12:00 8
И в чём проблема?
0
Ultrator
14 / 10 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:32 9
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
07.06.2009, 15:42 10
Цитата Сообщение от Ultrator Посмотреть сообщение
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
не понял, почему их будет ДВА?
будет один.
а в качестве координаты острова - брать левый верхний угол, к примеру.
для однозначной идентификации.
0
Ultrator
14 / 10 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:44 11
Ой, точно.
0
Трой
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 нешарю.
Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
08.06.2009, 07:06 13
если я сделаю так, как считаю нужным, работать будет очень быстро и точно, но препод может не понять...
я 15 лет системы распознавания образов разрабатываю.
это задание - частный случай, и довольно простой.
лучше так: Трой, пиши как сам понимаешь, и как умеешь, а мы доделаем, если что не работает.
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 19:04  [ТС] 14
Patch
Ну когда я говорил, что дальше cout и cin не шарю это была правда

Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
08.06.2009, 19:54 15
Цитата Сообщение от Трой Посмотреть сообщение
Ну когда я говорил, что дальше cout и cin не шарю это была правда
блин, ты-же писать умеешь?
по русски?
зайди на ядекс и спроси: "массивы в c c++"
узнаешь, как их делать.
и делай себе наздоровье.
я лет 15 назад Assembler и С изучал, так у меня была ОДНА растрепанная книга.
почти все делал методом научного тыка, потому как интернета тогда на 600км вокруг небыло, и спросить было не у кого.
а у вас вся информация под рукой...
так нет, лень-матушка...
ленишся читать и думать - иди в раздел "Заказ программ". с деньгами.
1
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
09.06.2009, 20:50  [ТС] 16
Patch
Этим заниматься я буду позже, тобиш летом когда время будет, а на данный момент у меня сроки поджимают и сделать эту задачу надо срочно. В то же время денег на счету нету. Даже на балансе трнета -полтора бакса и сижу в кредите.
Не думал, что так сложно будет написать код за так. Алчных и жадных людей стало много. Эх Вы!
0
Evg
Эксперт CАвтор FAQ
19306 / 7161 / 533
Регистрация: 30.03.2009
Сообщений: 20,042
Записей в блоге: 30
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;
}
2
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
10.06.2009, 22:52  [ТС] 18
Evg
Огромное, человеческое тебе спасибо!
зы За предыдущий пост извеняюсь, погоречился.
0
Evg
Эксперт CАвтор FAQ
19306 / 7161 / 533
Регистрация: 30.03.2009
Сообщений: 20,042
Записей в блоге: 30
10.06.2009, 22:57 19
Цитата Сообщение от Трой Посмотреть сообщение
зы За предыдущий пост извеняюсь, погоречился.
С каждым бывает
0
10.06.2009, 22:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2009, 22:57

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование)
Разработать программу с использованием наследования классов, реализующую...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать класс Книга поля: название книги,количество страниц,год издания...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран...


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

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

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