Помощь - Поиск - Пользователи - Календарь
Полная версия: Острова
Форум «Всё о Паскале» > Pascal, Object Pascal > Написание игр
@^WARlock^@
Народ помогите написать программу.


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

Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во.
Lapp
Не совсем понятно, в чем проблема. Если одна клетка - один остров, то просто посчитать количество ненулевых элементов в массиве, да и все..

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

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

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

Мне тоже не понятно... @^WARlock^@ поконкретней опиши задучу.
@^WARlock^@
Проблема в том.
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
Lapp
Цитата(@^WARlock^@ @ 1.03.2007 10:31) *

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

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

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

Пожалуйста, ставь условие четко и ясно..
T i m e
Цитата
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.

Используй чтение клавиши с помощью: key := readkey; В key в этом случае записывается прочитанная клавиша с клавиатуру. Пусть у тебя выделена какая то клетка в начале. Далее сделай так, чтобы по нажатии клавишей вверх, вниз, влево, вправо - твоя клетка передвигалась соответственно. Т.е. когда пользователь нажимает влево - выделение надо стереть и нарисовать снова на одну клетку левее. При передвижение запоминаются координаты выделенной клетки, чтобы по нажатию пользователем, к примеру, клавиши Enter мы смогли выйти на нужную клетку поля. Т.е. условие key = Enter как раз можно поставить на выход из нашего цикла.
P.S. Ну и конечно на передвижение нашей выделительной клетки надо поставить ограничения, чтобы она не выбегала за пределы поля smile.gif
TarasBer
Цитата(T i m e @ 1.03.2007 17:59) *

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


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

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

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

Ты думаешь ему нужен самый продвинутый метод... Я сомневаюсь... Помоему readkey - эелементарный для освоения. yes2.gif
P.S. Исходный вопрос почему то ушёл на второстепенный... А как ответить на тот вопрос который задан не конкретно я не знаю. Я кстати уже просил его типа уточнить, но на это пришёл второстепенный вопрос... nea.gif
Lapp
TarasBer, а чем тебе так не понравился ReadKey?
Человек (я имею в виду T i m e) предложил способ решения, причем в рамках Turbo Pascal - в чем он не прав? Кстати, ты даже не написал, что, по-твоему, следует использовать взамен ReadKey (ну, кроме обработки прерывания).
Кстати, чтобы использовать ReadKey, совсем не обязательно его любить. mad.gif

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

Что есть "обход в глубину или в ширину"? Нырять при этом не нужно?.. smile.gif
@^WARlock^@
Взял морской бой и убрал лишнее.

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


Вот, что я имел ввиду:
Нажмите для просмотра прикрепленного файла

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

2) Кто подскажит код по которому можно подсчитать кол-во островов.
volvo
2 Time: ты наказан? Вот и сиди в карцере! Еще один пост - тема просто закроется... Благодарить автор темы будет тебя. Все ясно?
TarasBer
Цитата(Lapp @ 2.03.2007 5:50) *

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

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

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

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

Но всетаки:

Цитата
2) Кто подскажит код по которому можно подсчитать кол-во островов.
Lapp
Цитата(@^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, это все слова. Предложи конкретный алгоритм, если уж говоришь о нем. А зоадно скажи, чем тебе не по нраву тот, который я привел в первом ответе.
@^WARlock^@
Цитата
И хотя бы намекни, что же ты хочешь иметь в конце. Просто посчитать острова?..


Да просто подсчитать острова, их кол-во должно отображаться на экране.
@^WARlock^@
Эот код действителен если остров состоит из одной клетки.
Код
s:=0;
for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];


А если мой остров состоит не из одной клетки, а более. Подскажите код, по которому можно подсчитать их кол-во.
Lapp
Цитата(@^WARlock^@ @ 25.03.2007 12:40) *

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

@^WARlock^@, с этого я и начал когда-то smile.gif. Смотри мой первый пост..
@^WARlock^@
Я его уже смотрел, но не смог реализовать.
Lapp
Мне неясно - в чем именно трудность?
Я сейчас тупо по написанному составил код - и он работает.
Может, он поможет тебе разобраться.
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.
@^WARlock^@
Проссмотрел выше указанный код, начиная с {реализации алготма} подставил в свою программу.
Теперь при выделении парных(т.е. из 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


Нажмите для просмотра прикрепленного файла
Lapp
Цитата(@^WARlock^@ @ 28.03.2007 5:30) *

Из-за чего так получается?

Насколько я смог понять, в твоей программе острова обозначены единицами. В моем алгоритме они обозначены -1 (минус единицами). Мне кажется, это вполне может вызвать такое поведение.
Выходов, как всегда, два:
1. Переделать мой код (не оченб красиво будет, но можно)
2. Поменять обозначение острова у тебя на -1.
Думай..

PS
Вообще, в твоей программе трудно разбираться.. Форматирование ты презираешь как класс? Даже мой кусок выровнял в линеечку - я еле узнал его..
@^WARlock^@
С подсчетом островов я разобрался.
Нажмите для просмотра прикрепленного файла

Как теперь сделать все в графическом режиме, поле и сетку нарисовать смогу, а как перемещаться поэтой сетке(для выделения острова) и сделать так, чтоб масив заполнялся путем выделения клетки в этой сетке?
@^WARlock^@
Так, как можно заполнять массив в графическом режиме?
Lapp
Молодец, прога, вроде, работает! smile.gif
Цитата(@^WARlock^@ @ 7.04.2007 14:03) *

как можно заполнять массив в графическом режиме?

Заполнять - точно так же. Нужно поменять только интнрфейс.
Я не совсем понимаю, зачем ты сделал юнит ENGINE.. Вот выделить интерфейс в отдельный юнит - это было бы правильно. Тогда замена текста на графику состояла бы в написании нового юнита - и все. Попробуй разделить engine на два юнита, выделив графику.
А как писать - аналогично.. Только использовать графику: Line, Rectangle, Bar, OutTextXY.. - и т.д. т.п. smile.gif. Начни и показывай..

PS
а форматирование у тебя все так же на нуле.. sad.gif Читать такие программы удовольствия мало. Учти, это затрудняет тех, кто отвечает тебе (если уж тебе самому все равно) с соответствующим результатом..
@^WARlock^@
Цитата
Попробуй разделить engine на два юнита, выделив графику.

На какие и как? Просто располовинить? blink.gif

Вот добавил новый юнит GRAFICA, из предыдущих островов. В графическом режиме вылазиет поле, и можно управлять мышью. А как состыковать это все с моей задачей, что-то придумать не могу. Труба полная mega_chok.gif .
Нажмите для просмотра прикрепленного файла
Lapp
Цитата(@^WARlock^@ @ 9.04.2007 11:06) *

На какие и как? Просто располовинить?
...
Труба полная

Попробуй отделить все, что относится к отображению в отдельный юнит. Скажем, твой DrawMap - это явно к отображению, а Schet - нет. Это я грубо, примерно. Остальные найди сам. Соответственно, и переменные разделить. Многое для этого придется переделать, задача сама по себе непростая. А потом по образу и подобию того юнита, который отображает текст, сделаешь юнит, который отображает в графике. Это потребует немалой работы, но зато в результате должно получиться следующее: нужна графика - подставляешь юнит с графикой, нужен текст - подставляешь текстовый..

PS
Еще раз поторяю: разберись с форматированием программного текста. Если снова проигнорируешь мой совет - я тоже буду игнорировать твои вопросы. Я не имею в виду, что ты сразу все правильно отфоматируешь, но хотя бы обратить на это внимание - необходимо!
@^WARlock^@
Цитата
Еще раз повторяю: разберись с форматированием программного текста. ...

Вот понавтыкал пробелов, может лучше будет.

А вот в этом случае идет заполнение мвссива?
Нажмите для просмотра прикрепленного файла
Если идет, то я там добавил (Procedure SCHET). Не подскажите, как в графмческом режиме вывести числовую переменную. В данном случае результат процедуры (SCHET).
Lapp
Цитата(@^WARlock^@ @ 12.04.2007 6:21) *

как в графмческом режиме вывести числовую переменную.

Процедура OutTextXY. Только сначала переведи ее а строку.
Прогу гляну чуть позже..
@^WARlock^@
В моей последней проге идет хоть какое-то заполнение массива, или нет?
@^WARlock^@
Как и "все", я решил забить на подключение графики к моей проге.

Я оредактировал мою старую прогу и вот, что получилось:
Нажмите для просмотра прикрепленного файла
@^WARlock^@
Народ, подскажите алгоритм выполнения подсчета островов или блок схему процедуры подсчета островов.

Процедура подсчета островов:
.....
Procedure Schet;
Var
n:integer;
begin
n:=mx*my;
for wy:=1 to my do
for wx:=1 to mx do
if (Z[wx,wy]=1) and (Z[wx,wy+1]<>1) and (Z[wx+1,wy]<>1) and
(Z[wx,wy-1]<>1) and (Z[wx-1,wy]<>1) then
begin
Inc(n);
Z[wx,wy]:=n;
end;
for wy:=1 to my do
for wx:=1 to mx do
if (Z[wx,wy]=1) and (Z[wx,wy+1]<mx*my) and (Z[wx+1,wy]<mx*my) and
(Z[wx,wy-1]<mx*my) and (Z[wx-1,wy]<mx*my) then
begin
Inc(n);
Z[wx,wy]:=n;
end
else if(Z[wx,wy]=1) then
begin
if (Z[wx,wy+1]>mx*my) then Z[wx,wy]:=Z[wx,wy+1];
if (Z[wx+1,wy]>mx*my) then Z[wx,wy]:=Z[wx+1,wy];
if (Z[wx,wy-1]>mx*my) then Z[wx,wy]:=Z[wx,wy-1];
if (Z[wx-1,wy]>mx*my) then Z[wx,wy]:=Z[wx-1,wy];
end;
write(n-mx*my);
end;
.....


Я как бы сделал блок схему, и алгоритм проги, но мне сказали после условия "Если поле заполнено", подробно расписать, как происходит подсчет островов.

 ! 
@^WARlock^@, файлы .doc прикреплять запрещено (читай Правила). Файл удален.
Lapp

Lapp
Цитата(@^WARlock^@ @ 22.04.2007 7:09) *

Народ, подскажите алгоритм выполнения подсчета островов или блок схему процедуры подсчета островов.
...
Я как бы сделал блок схему, и алгоритм проги, но мне сказали после условия "Если поле заполнено", подробно расписать, как происходит подсчет островов.

Твоя процедура работает неправильно.. Нет смысла, думаю, составлять алгоритм или блок-схему по неверной процедуре. Вот, смотри - тут приведены острова, потом выводится результат твоей процедуры, а потом сама матрица, где можно видеть, как ты считал острова. Видно, что один и тот же остров помечен разными цифрами. Волны означают воду.. smile.gif
Код
~~~~~~~~
XXXXXXXX
~XX~~~X~
X~~~XXX~
X~XX~~~X
~~XXX~XX
X~XX~XXX
~XXX~XXX

9

~~~~~~~~
22222222
~22~~~2~
3~~~444~
3~55~~~6
~~555~77
1~55~888
~999~888

@^WARlock^@ - чисто по-человечески, скажи, почему ты сначала задаешь вопрос, тебе отвечают, потом ты делаешь все по-другому, а потом снова просишь ответить на вопрос, на который уже отвечено в самом первом посте темы?..
Это вызываает недоумение.. Есть ли смысл говорить, если собеседник не слышит?
@^WARlock^@
Цитата
Твоя процедура работает неправильно.

Точно, а я и не замечал(наверное потомучто больше 4-6 островов не выделял). Не подскажите, из-за чего так происходит?
И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.
Lapp
Цитата(@^WARlock^@ @ 22.04.2007 13:58) *

Не подскажите, из-за чего так происходит?
И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.

Я тебя решительно не понимаю.. Советов не слушаешь, на вопросы не отвечаешь - я умываю руки..
@^WARlock^@
Цитата
Советов не слушаешь, на вопросы не отвечаешь


Советы, по поводу того, что процдура SCHET не корректно работает, я обратил внимание перепроверил, да это действительно так.
На какие вопросы я не отвечаю?
Мне кажется, что совсем наоборот, мои вопросы ни кто не замечат.
Lapp
Цитата(@^WARlock^@ @ 24.04.2007 6:39) *

На какие вопросы я не отвечаю?

Вот на этот:
@^WARlock^@ - чисто по-человечески, скажи, почему ты сначала задаешь вопрос, тебе отвечают, потом ты делаешь все по-другому, а потом снова просишь ответить на вопрос, на который уже отвечено в самом первом посте темы?..
Это вызываает недоумение.. Есть ли смысл говорить, если собеседник не слышит?
Lapp
Цитата(@^WARlock^@ @ 22.04.2007 13:58) *

И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.

Мой совет: вернись к началу, и возьми мою процедуру в точности в том виде, в котором она есть. Я понимаю, тебя не устраивает, что в ней острова обозначены -1, а не 1. Поменяй в моей процедуре все знаки на обратные. То есть острова обозначай 1, а их номера - отрицательными числами. Это самый простой способ, имхо..
Тогда и алгоритм будет один в один. Сможешь взять прямо из первого мессаджа. Что непонятно - я объясню.. smile.gif

PS
ты извини за наезды, просто старайся внимательно читать советы и придерживаться их. Либо говори, почему делаешь иначе. Ведь это же двусторонний разговор, так? smile.gif

Добавлено через 4 мин.
Но будет значительно красивее, если ты в своей части переделаешь 1 на -1. По-хорошему, вообще не нужно привязываться к конкретному числу. Просто сделай константу - скажем, Terra = -1. При заполнении островов используй ее. Нигде не пользуйся явно минус единицей или единицей. Вот подсчет - это другое дело. Номер должен быть явно.
Улавливаешь идею?
Говори тут активней, тогда результат будет лучше.
Успехов!
@^WARlock^@
Не понимаю почему я тупил столько времени.
LAPP - видимо всетаки ты отчасти был прав, на счет того, что я не слушаю советов.
Например вот этот.
Цитата
Поменять обозначение острова у тебя на -1.


Я поменял у себя обозначения острова, и вродибы прога стала работать как надо.
Нажмите для просмотра прикрепленного файла

Надеюсь теперь ты мне поможешь реализовать блок-схему процедуры SCHET.

И еще такой нюанс, как сделать, чтобы мой PASCAL распознавал русский язык.

Lapp
Цитата(@^WARlock^@ @ 27.04.2007 12:02) *

Не понимаю почему я тупил столько времени.
Бывает.. одни тупят, другие ждут у них просветления. Главное - дождаться.. smile.gif
Цитата(@^WARlock^@ @ 27.04.2007 12:02) *

видимо всетаки ты отчасти был прав, на счет того, что я не слушаю советов.
Фраза сказана предельно осторожно, но если ты действительно это понял хоть немного - это самое большое твое (и немного мое smile.gif) достижение в этой работе. Программирование на втором месте..
Цитата(@^WARlock^@ @ 27.04.2007 12:02) *

Надеюсь теперь ты мне поможешь реализовать блок-схему процедуры SCHET.
Помогу обязательно! Только сначала высплюсь.. smile.gif
Цитата(@^WARlock^@ @ 27.04.2007 12:02) *

И еще такой нюанс, как сделать, чтобы мой PASCAL распознавал русский язык.
Этот вопрос много раз обсуждался, есть надежные способы. Признаться, я по ним не спец..
@^WARlock^@
LAPP - говорил, что поможешь реализовать блок-схему процедуры SCHET, а сам пропал куда-то.
Lapp
Цитата(@^WARlock^@ @ 2.05.2007 5:23) *

LAPP - говорил, что поможешь реализовать блок-схему процедуры SCHET, а сам пропал куда-то.

А разве ты уже выложил последний рабочий вариант программы?..
Я слежу и каждый день проверяю..

Добавлено через 1 мин.
Кроме того, помочь - не значит сделать за тебя.
Ты выложи, что сделал (как ты это сделал со старым вариантом), я посмотрю и подправлю.. Ок?
@^WARlock^@
Последний рабочий вариант программы:
Нажмите для просмотра прикрепленного файла

Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов. Может тогда и придумаю, как нарисовать блок-схему.
Lapp
Цитата(@^WARlock^@ @ 2.05.2007 7:39) *

Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов

Сейчас попробую вспомнить..
Я просто введу комментарии в тот агоритм в первом посте.
Lapp
1. Обнуляем счетчик островов N.
Ну, это понятно.

2. Проходим по всему массиву до встречи первой -1.
Тоже понятно - идем до встречи с нехоженой землей. В самом начале в нашем массиве есть только 0 (вода) и -1 (земля). Затем земля перемаркировывается номером острова. Но -1 всегда означает землю, на которой мы еще не были (где не ступала нога человека smile.gif).

3. Если ни одной -1 не было найдено - выходим.
И это понятно - неизведанные земли кончились. Выход из процедуры.

4. Увеличиваем N на 1.
Если нашли -1 - значит, нашли новый остров. Увеличиваем счетчик островов.

5. Меняем значение найденной клетки на N.
Столбим землю. Вместо -1 записываем номер острова

6. Сбрасываем флаг.
Флаг будет установлен, если мы найдем новые клетки этого же острова (то есть -1 соседние к N). Он нужен нам, чтобы понять, когда закончится процесс перемаркировки текущего (N-го) острова.

7. Проходим циклом по всему массиву. Если текущий элемент равен -1, а один из его четырех соседей равен N, то меняем его на N и устанавливаем флаг.
Цикл по всему массиву - это двойной цикл по координатам, как обычно (по строчкам, сверху вниз). Перемаркировка текущего острова производится не за один цикл. Это я поясню потом на примере

8. Если флаг установлен - переходим к п.6
Установленный флаг означает, что соседние клетки были найдены. А это значит, что могут быть и соседние к новым найденным. Значит, надо пройти еще раз..

9. Если флаг сброшен - переходим к п.2
Сброшенный флаг значит, что за последний проход не было найдено новых соседних клеток к текущему острову. Значит, мы нашли все. Можно переходить к поиску нового острова.

Вот пример.
Представь себе остров, закрученный наподобие спирали (# означает -1, а ~ - воду, то есть 0 ):
Код
~~~~~~~~~~~~
~##########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

Когда мы его только нашли, ситуация такая:

~~~~~~~~~~~~
~1#########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

После первого прохода мы получим:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~#~1~
~11111111~1~
~~~~~~~~~~~~

Перемаркированы только те клетки, которые правее-ниже от пройденных.

После 2-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 3-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

Медленно продвигаемся наверх, по клетке за проход по всей матрице..
....
После 9-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~##1111~1~
~1~#~~~~1~1~
~1~#~~#~1~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

.....


После 11-го остается только одна клетка:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~111111~1~
~1~1~~~~1~1~
~1~1~~#~1~1~
~1~1111~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 12-го все клетки закрашены, но флаг все же установлен.
На 13-м проходе флаг установлен не будет: больше нет -1, соседних к 1.

Вот так. Алгоритм небыстрый, но работает корректно, не собъется ни на какой самой запутанной комбинации.

Ну что, сможешь составить блок-схему? smile.gif
@^WARlock^@
У меня вот, что получилось:
Нажмите для просмотра прикрепленного файла
Lapp
Цитата(@^WARlock^@ @ 2.05.2007 11:00) *

У меня вот, что получилось:

Пока что сыровато, я не стал вникать. Так в принципе направление верное.
В конце есть явная ошибка: выхода в конце нет и быть не может! Выход только в п.4.
И почему ты называешь выход "выводом"?..
@^WARlock^@
Цитата
Пока что сыровато

Я в блок-схемах не силен. Может тогда предложишь свой вариант.
@^WARlock^@
Цитата
И почему ты называешь выход "выводом"?

Как я понял, это выход в твоей проге, а в моей это вывод кол-ва островов, поэтому и "вывод".

Не много откорректировал блок-схему:
Нажмите для просмотра прикрепленного файла
Lapp
Цитата(@^WARlock^@ @ 2.05.2007 12:40) *

Я в блок-схемах не силен. Может тогда предложишь свой вариант.

Я вообще им не обучался..

Вот мой вариант: Нажмите для просмотра прикрепленного файла

В принципе, "поиск -1" тоже можно расписать. Но это уж ты сам, если захочешь..
@^WARlock^@
Решил перед сдачей проги окончательно её протестировать, и вот те здравствуйте,
каккой-то глюк:

1)Ввожу острова, их кол-во выводится правильно, в данном случае (14).

X~~XX~X~~~
~X~~~X~X~~
X~X~X~X~~~
~X~X~~~~~~
X~X~~~~~~~
~~~~~~~~~~

2)Снова ввожу острова, кол-во выводится либо правильно, либо почти.
3)Ввожу ту же комбнацию, что и в 1-ом случае, совершенно друго результат.


Может ли это связано с тем, что отчистку поля я осуществляю путем отчистки экрана, а не массива
или куда там производится запись результатаов.

Подскажите, как от него(глюка) избавиться.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.