IPB
ЛогинПароль:

3 страниц V  1 2 3 >  
 Ответить  Открыть новую тему 
> Острова
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Народ помогите написать программу.


Острова (определить кол-во островов на озере).

Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Не совсем понятно, в чем проблема. Если одна клетка - один остров, то просто посчитать количество ненулевых элементов в массиве, да и все..

Вот если острова, соседствующие через сторону, считать одним островом - тогда да, есть некоторая проблема.
Допустим, море представлено двумерным массивом целых. В нем 0 означает воду, а -1 (минус единица) - остров. Тогда алгоритм подсчета можно сделать таким (дубово, но работать будет)..

1. Обнуляем счетчик островов N.
2. Проходим по всему массиву до встречи первой -1.
3. Если ни одной -1 не было найдено - выходим.
4. Увеличиваем N на 1.
5. Меняем значение найденной клетки на N
6. Сбрасываем флаг.
7. Проходим циклом по всему массиву. Если текущий элемент равен -1, а один из его четырех соседей равен N, то меняем его на N и устанавливаем флаг.
8. Если флаг установлен - переходим к п.6
9. Если флаг сброшен - переходим к п.2

После выполнения алгоритма в N будет лежать число островов, а сами острова в массиве будут помечены клетками, содержащими номер острова.
Этот алгоритм наверняка можно ускорить.. Нужно?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 27
Пол: Мужской

Репутация: -  -1  +


Цитата
Не совсем понятно, в чем проблема.

Мне тоже не понятно... @^WARlock^@ поконкретней опиши задучу.


--------------------
Time have not meaning. Mind - this is main...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Проблема в том.
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(@^WARlock^@ @ 1.03.2007 10:31) *

Проблема в том.
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.

Но.. @^WARlock^@, уважаемый - почему же ты в первом сообщении написал совершенно другое??.. blink.gif
Н-да..

К тому же - не могу сказать, чтоб сейчас твоя постановка задачи блистала ясностью.. Что значит "выделить"? Это типа как поджелудочная железа выделяет желудочный сок?

Пожалуйста, ставь условие четко и ясно..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 27
Пол: Мужской

Репутация: -  -1  +


Цитата
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.

Используй чтение клавиши с помощью: key := readkey; В key в этом случае записывается прочитанная клавиша с клавиатуру. Пусть у тебя выделена какая то клетка в начале. Далее сделай так, чтобы по нажатии клавишей вверх, вниз, влево, вправо - твоя клетка передвигалась соответственно. Т.е. когда пользователь нажимает влево - выделение надо стереть и нарисовать снова на одну клетку левее. При передвижение запоминаются координаты выделенной клетки, чтобы по нажатию пользователем, к примеру, клавиши Enter мы смогли выйти на нужную клетку поля. Т.е. условие key = Enter как раз можно поставить на выход из нашего цикла.
P.S. Ну и конечно на передвижение нашей выделительной клетки надо поставить ограничения, чтобы она не выбегала за пределы поля smile.gif

Сообщение отредактировано: T i m e -


--------------------
Time have not meaning. Mind - this is main...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Цитата(T i m e @ 1.03.2007 17:59) *

Используй чтение клавиши с помощью: key := readkey; В key в этом случае записывается прочитанная клавиша с клавиатуру. Пусть у тебя выделена какая то клетка в начале. Далее сделай так, чтобы по нажатии клавишей вверх, вниз, влево, вправо - твоя клетка передвигалась соответственно. Т.е. когда пользователь нажимает влево - выделение надо стереть и нарисовать снова на одну клетку левее. При передвижение запоминаются координаты выделенной клетки, чтобы по нажатию пользователем, к примеру, клавиши Enter мы смогли выйти на нужную клетку поля. Т.е. условие key = Enter как раз можно поставить на выход из нашего цикла.
P.S. Ну и конечно на передвижение нашей выделительной клетки надо поставить ограничения, чтобы она не выбегала за пределы поля smile.gif


Исходный вопрос какой был? Сосчитать кол-во островов!
Или вы предлагаете пользователю при помощи стрелочек и ентера по одному выделить все острова, и чтобы в переменную-счётчик записывалось количество нажатий ентера? Не смешно.
И почему вы так реадкей любите? А давайте я стану всем советовать вешаться на $09 прерывание и смотреть в порт $60! Ведь это самый продвинутый способ чтения с клавиатуры! (у него есть плюсы - возможность фиксирования нажатия нескольких клавиш, и он видит и различает ЛЮБУЮ клавишу, включая правый и левый альт итд).

Для выделения острова можно:
1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например).
2. Все эти клетки обвести в квадратную рамочку, выводя ксором. Тогда общая граница двух соседних клеток, относящихся к острову, будет обведена 2 раза, то есть вообще как будто бы не обведена (свойство такое у ксора). По углам аналогично.
А для снятия выделения надо обвести все это клетки ещё раз.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 27
Пол: Мужской

Репутация: -  -1  +


Цитата
Исходный вопрос какой был? Сосчитать кол-во островов!
Или вы предлагаете пользователю при помощи стрелочек и ентера по одному выделить все острова, и чтобы в переменную-счётчик записывалось количество нажатий ентера? Не смешно.

Я отвечал не на исходный вопрос, а на тот который и указал в цитате выше по поводу перемещения по полю.
Цитата
И почему вы так реадкей любите? А давайте я стану всем советовать вешаться на $09 прерывание и смотреть в порт $60! Ведь это самый продвинутый способ чтения с клавиатуры!

Ты думаешь ему нужен самый продвинутый метод... Я сомневаюсь... Помоему readkey - эелементарный для освоения. yes2.gif
P.S. Исходный вопрос почему то ушёл на второстепенный... А как ответить на тот вопрос который задан не конкретно я не знаю. Я кстати уже просил его типа уточнить, но на это пришёл второстепенный вопрос... nea.gif

Сообщение отредактировано: T i m e -


--------------------
Time have not meaning. Mind - this is main...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


TarasBer, а чем тебе так не понравился ReadKey?
Человек (я имею в виду T i m e) предложил способ решения, причем в рамках Turbo Pascal - в чем он не прав? Кстати, ты даже не написал, что, по-твоему, следует использовать взамен ReadKey (ну, кроме обработки прерывания).
Кстати, чтобы использовать ReadKey, совсем не обязательно его любить. mad.gif

И еще, поясни, пожалуйста, слова:
1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например).

Что есть "обход в глубину или в ширину"? Нырять при этом не нужно?.. smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Взял морской бой и убрал лишнее.

Цитата
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.


Вот, что я имел ввиду:
Прикрепленный файл  ОСТРОВА.rar ( 75.23 килобайт ) Кол-во скачиваний: 522


Тут и поле готовое, и острова можно выд не перемещаясь по клеткам.

2) Кто подскажит код по которому можно подсчитать кол-во островов.

Сообщение отредактировано: @^WARlock^@ -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






2 Time: ты наказан? Вот и сиди в карцере! Еще один пост - тема просто закроется... Благодарить автор темы будет тебя. Все ясно?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Цитата(Lapp @ 2.03.2007 5:50) *

TarasBer, а чем тебе так не понравился ReadKey?
Человек (я имею в виду T i m e) предложил способ решения, причем в рамках Turbo Pascal - в чем он не прав? Кстати, ты даже не написал, что, по-твоему, следует использовать взамен ReadKey (ну, кроме обработки прерывания).
Кстати, чтобы использовать ReadKey, совсем не обязательно его любить. mad.gif

И еще, поясни, пожалуйста, слова:
1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например).

Что есть "обход в глубину или в ширину"? Нырять при этом не нужно?.. smile.gif

Я извиняюсь, просто меня проглючило немного... Я от Варлока увидел только вопросы о том, как определить сколько островов, и как выделить остров. А как организовать перемещение - я не заметил. Вот и показался мне ответ Времени не в тему. Разумеется, я не против редкея, в данном случае его вполне хватает. Про порты - это я переборщил. Извиняюсь, я не прав.
А обход - это если остров состоит из нескольких клеток - то мы сначала находим клетку, которая относится к острову, а потом обходом (не, нырять не стоит) находим все клетки, до которых из неё можно добраться по суше.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Вижу вы тут спор затеяли.

Но всетаки:

Цитата
2) Кто подскажит код по которому можно подсчитать кол-во островов.


Сообщение отредактировано: @^WARlock^@ -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(@^WARlock^@ @ 4.03.2007 12:45) *
Вижу вы тут спор затеяли.
@^WARlock^@, спор, как ты выражаешься, был затеян по одной только причине: из твоих "условий" никто не смог понять, что же тебе все-таки нужно! Ты не обратил внимания на вопросы? Твои "пояснения", увы, мало помогли.. Когда задешь вопрос, старайся дать исчерпывающую информацию об условии - даже если это требует нескольких лишних строчек текста. Поимей уважение к отвечающим..
Цитата(@^WARlock^@ @ 3.03.2007 7:26) *
Взял морской бой и убрал лишнее.
...
Тут и поле готовое, и острова можно выд не перемещаясь по клеткам.
Поле-то готовое, но только ты выкинул часть, где расставляются корабли (в твоем случае - острова, как я понял). Нажатие мышки в этой программе соответствует выстрелу, после чего проверяется попадание. У тебя же, поскольку массив не заполнен, никакого попадания нет.
Цитата(@^WARlock^@ @ 4.03.2007 12:45) *
2) Кто подскажит код по которому можно подсчитать кол-во выделенных клеток(островов).
Для начала - введи заполнение массива. Если хочешь делать это мышью - значит просто ставь 1 в соответствующий элемент массива ac. И убери проверку на попадание...
Подсчет островов - это будет просто двойной цикл суммирования:
s:=0;
for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];
Ты это хотел? У меня все меньше уверенности, что я тебя правильно понимаю..
И хотя бы намекни, что же ты хочешь иметь в конце. Просто посчитать острова?..

Цитата(TarasBer @ 3.03.2007 19:07) *
А обход - это если остров состоит из нескольких клеток - то мы сначала находим клетку, которая относится к острову, а потом обходом (не, нырять не стоит) находим все клетки, до которых из неё можно добраться по суше.
TarasBer, это все слова. Предложи конкретный алгоритм, если уж говоришь о нем. А зоадно скажи, чем тебе не по нраву тот, который я привел в первом ответе.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Цитата
И хотя бы намекни, что же ты хочешь иметь в конце. Просто посчитать острова?..


Да просто подсчитать острова, их кол-во должно отображаться на экране.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Эот код действителен если остров состоит из одной клетки.
Код
s:=0;
for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];


А если мой остров состоит не из одной клетки, а более. Подскажите код, по которому можно подсчитать их кол-во.

Сообщение отредактировано: @^WARlock^@ -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(@^WARlock^@ @ 25.03.2007 12:40) *

если мой остров состоит не из одной клетки, а более. ... подсчитать их кол-во.

@^WARlock^@, с этого я и начал когда-то smile.gif. Смотри мой первый пост..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Я его уже смотрел, но не смог реализовать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Мне неясно - в чем именно трудность?
Я сейчас тупо по написанному составил код - и он работает.
Может, он поможет тебе разобраться.
const
mx=8;
my=8;
var
Z:array[1..mx,1..my]of integer;
i,j,x,y,n:integer;
Flag:boolean;


begin
{Задание массива случайным образом}
for j:=1 to my do for i:=1 to mx do Z[i,j]:=-Random(2);
for j:=1 to my do begin
for i:=1 to mx do case Z[i,j] of
0:Write('~');
-1:Write('X');
end;
WriteLn
end;
{Реализация алгоритма}
n:=0;
for y:=1 to my do for x:=1 to mx do if Z[x,y]=-1 then begin
Inc(n);
Z[x,y]:=n;
repeat
Flag:=false;
for j:=1 to my do for i:=1 to mx do
if (Z[i,j]=-1)and((i>1)and(Z[i-1,j]=n)or(i<mx)and(Z[i+1,j]=n)or(j>1)and(Z[i,j-1]=n)or(j<my)and(Z[i,j+1]=n))
then begin
Z[i,j]:=n;
Flag:=true
end
until not Flag
end;
WriteLn('Total islands: ',n);
ReadLn
end.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Проссмотрел выше указанный код, начиная с {реализации алготма} подставил в свою программу.
Теперь при выделении парных(т.е. из 2-ух клеток) и не парнх островов, в кол-ве пишется 0, а когда убираю минус перед единицейне(см. ниже) то прога считает по принципу одна клетка один остров.
Внимание вопрос.
Из-за чего так получается?

......
{Реализация алгоритма}
n:=0;
for y:=1 to my do
for x:=1 to mx do

if Z[x,y]=-1 then begin {Вот тут убираю минус}

Inc(n);
Z[x,y]:=n;
repeat
Flag:=false;
for j:=1 to my do for i:=1 to mx do
if (Z[i,j]=-1)and((i>1)and(Z[i-1,j]=n)or(i<mx)and(Z[i+1,j]=n)or(j>1)and(Z[i,j-1]=n)or(j<my)and(Z[i,j+1]=n))
then begin
Z[i,j]:=n;
Flag:=true
end
until not Flag
end;
WriteLn('Total islands: ',n);
......
ReadLn


Прикрепленный файл  OSTROVA.rar ( 9.15 килобайт ) Кол-во скачиваний: 483


Сообщение отредактировано: @^WARlock^@ -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

3 страниц V  1 2 3 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:22
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name