Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во.
Lapp
28.02.2007 17:43
Не совсем понятно, в чем проблема. Если одна клетка - один остров, то просто посчитать количество ненулевых элементов в массиве, да и все..
Вот если острова, соседствующие через сторону, считать одним островом - тогда да, есть некоторая проблема. Допустим, море представлено двумерным массивом целых. В нем 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
28.02.2007 22:42
Цитата
Не совсем понятно, в чем проблема.
Мне тоже не понятно... @^WARlock^@ поконкретней опиши задучу.
@^WARlock^@
1.03.2007 14:31
Проблема в том. 1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
Lapp
1.03.2007 15:32
Цитата(@^WARlock^@ @ 1.03.2007 10:31)
Проблема в том. 1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
Но.. @^WARlock^@, уважаемый - почему же ты в первом сообщении написал совершенно другое??.. Н-да..
К тому же - не могу сказать, чтоб сейчас твоя постановка задачи блистала ясностью.. Что значит "выделить"? Это типа как поджелудочная железа выделяет желудочный сок?
Пожалуйста, ставь условие четко и ясно..
T i m e
1.03.2007 21:59
Цитата
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
Используй чтение клавиши с помощью: key := readkey; В key в этом случае записывается прочитанная клавиша с клавиатуру. Пусть у тебя выделена какая то клетка в начале. Далее сделай так, чтобы по нажатии клавишей вверх, вниз, влево, вправо - твоя клетка передвигалась соответственно. Т.е. когда пользователь нажимает влево - выделение надо стереть и нарисовать снова на одну клетку левее. При передвижение запоминаются координаты выделенной клетки, чтобы по нажатию пользователем, к примеру, клавиши Enter мы смогли выйти на нужную клетку поля. Т.е. условие key = Enter как раз можно поставить на выход из нашего цикла. P.S. Ну и конечно на передвижение нашей выделительной клетки надо поставить ограничения, чтобы она не выбегала за пределы поля
TarasBer
2.03.2007 0:16
Цитата(T i m e @ 1.03.2007 17:59)
Используй чтение клавиши с помощью: key := readkey; В key в этом случае записывается прочитанная клавиша с клавиатуру. Пусть у тебя выделена какая то клетка в начале. Далее сделай так, чтобы по нажатии клавишей вверх, вниз, влево, вправо - твоя клетка передвигалась соответственно. Т.е. когда пользователь нажимает влево - выделение надо стереть и нарисовать снова на одну клетку левее. При передвижение запоминаются координаты выделенной клетки, чтобы по нажатию пользователем, к примеру, клавиши Enter мы смогли выйти на нужную клетку поля. Т.е. условие key = Enter как раз можно поставить на выход из нашего цикла. P.S. Ну и конечно на передвижение нашей выделительной клетки надо поставить ограничения, чтобы она не выбегала за пределы поля
Исходный вопрос какой был? Сосчитать кол-во островов! Или вы предлагаете пользователю при помощи стрелочек и ентера по одному выделить все острова, и чтобы в переменную-счётчик записывалось количество нажатий ентера? Не смешно. И почему вы так реадкей любите? А давайте я стану всем советовать вешаться на $09 прерывание и смотреть в порт $60! Ведь это самый продвинутый способ чтения с клавиатуры! (у него есть плюсы - возможность фиксирования нажатия нескольких клавиш, и он видит и различает ЛЮБУЮ клавишу, включая правый и левый альт итд).
Для выделения острова можно: 1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например). 2. Все эти клетки обвести в квадратную рамочку, выводя ксором. Тогда общая граница двух соседних клеток, относящихся к острову, будет обведена 2 раза, то есть вообще как будто бы не обведена (свойство такое у ксора). По углам аналогично. А для снятия выделения надо обвести все это клетки ещё раз.
T i m e
2.03.2007 0:44
Цитата
Исходный вопрос какой был? Сосчитать кол-во островов! Или вы предлагаете пользователю при помощи стрелочек и ентера по одному выделить все острова, и чтобы в переменную-счётчик записывалось количество нажатий ентера? Не смешно.
Я отвечал не на исходный вопрос, а на тот который и указал в цитате выше по поводу перемещения по полю.
Цитата
И почему вы так реадкей любите? А давайте я стану всем советовать вешаться на $09 прерывание и смотреть в порт $60! Ведь это самый продвинутый способ чтения с клавиатуры!
Ты думаешь ему нужен самый продвинутый метод... Я сомневаюсь... Помоему readkey - эелементарный для освоения. P.S. Исходный вопрос почему то ушёл на второстепенный... А как ответить на тот вопрос который задан не конкретно я не знаю. Я кстати уже просил его типа уточнить, но на это пришёл второстепенный вопрос...
Lapp
2.03.2007 9:50
TarasBer, а чем тебе так не понравился ReadKey? Человек (я имею в виду T i m e) предложил способ решения, причем в рамках Turbo Pascal - в чем он не прав? Кстати, ты даже не написал, что, по-твоему, следует использовать взамен ReadKey (ну, кроме обработки прерывания). Кстати, чтобы использовать ReadKey, совсем не обязательно его любить.
И еще, поясни, пожалуйста, слова:
1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например).
Что есть "обход в глубину или в ширину"? Нырять при этом не нужно?..
@^WARlock^@
3.03.2007 11:26
Взял морской бой и убрал лишнее.
Цитата
1) Допустим я сделал поле, как перемещаться по этому полю, и как выделить остров.
Тут и поле готовое, и острова можно выд не перемещаясь по клеткам.
2) Кто подскажит код по которому можно подсчитать кол-во островов.
volvo
3.03.2007 19:24
2 Time: ты наказан? Вот и сиди в карцере! Еще один пост - тема просто закроется... Благодарить автор темы будет тебя. Все ясно?
TarasBer
3.03.2007 23:07
Цитата(Lapp @ 2.03.2007 5:50)
TarasBer, а чем тебе так не понравился ReadKey? Человек (я имею в виду T i m e) предложил способ решения, причем в рамках Turbo Pascal - в чем он не прав? Кстати, ты даже не написал, что, по-твоему, следует использовать взамен ReadKey (ну, кроме обработки прерывания). Кстати, чтобы использовать ReadKey, совсем не обязательно его любить.
И еще, поясни, пожалуйста, слова:
1. Определить все клетки, относящиеся к острову (обходом в глубину или в ширину, например).
Что есть "обход в глубину или в ширину"? Нырять при этом не нужно?..
Я извиняюсь, просто меня проглючило немного... Я от Варлока увидел только вопросы о том, как определить сколько островов, и как выделить остров. А как организовать перемещение - я не заметил. Вот и показался мне ответ Времени не в тему. Разумеется, я не против редкея, в данном случае его вполне хватает. Про порты - это я переборщил. Извиняюсь, я не прав. А обход - это если остров состоит из нескольких клеток - то мы сначала находим клетку, которая относится к острову, а потом обходом (не, нырять не стоит) находим все клетки, до которых из неё можно добраться по суше.
@^WARlock^@
4.03.2007 16:45
Вижу вы тут спор затеяли.
Но всетаки:
Цитата
2) Кто подскажит код по которому можно подсчитать кол-во островов.
Lapp
6.03.2007 8:55
Цитата(@^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^@
6.03.2007 13:23
Цитата
И хотя бы намекни, что же ты хочешь иметь в конце. Просто посчитать острова?..
Да просто подсчитать острова, их кол-во должно отображаться на экране.
@^WARlock^@
25.03.2007 16:40
Эот код действителен если остров состоит из одной клетки.
Код
s:=0; for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];
А если мой остров состоит не из одной клетки, а более. Подскажите код, по которому можно подсчитать их кол-во.
Lapp
25.03.2007 16:43
Цитата(@^WARlock^@ @ 25.03.2007 12:40)
если мой остров состоит не из одной клетки, а более. ... подсчитать их кол-во.
@^WARlock^@, с этого я и начал когда-то . Смотри мой первый пост..
@^WARlock^@
25.03.2007 16:45
Я его уже смотрел, но не смог реализовать.
Lapp
25.03.2007 17:46
Мне неясно - в чем именно трудность? Я сейчас тупо по написанному составил код - и он работает. Может, он поможет тебе разобраться.
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^@
28.03.2007 8:30
Проссмотрел выше указанный код, начиная с {реализации алготма} подставил в свою программу. Теперь при выделении парных(т.е. из 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
Насколько я смог понять, в твоей программе острова обозначены единицами. В моем алгоритме они обозначены -1 (минус единицами). Мне кажется, это вполне может вызвать такое поведение. Выходов, как всегда, два: 1. Переделать мой код (не оченб красиво будет, но можно) 2. Поменять обозначение острова у тебя на -1. Думай..
PS Вообще, в твоей программе трудно разбираться.. Форматирование ты презираешь как класс? Даже мой кусок выровнял в линеечку - я еле узнал его..
Как теперь сделать все в графическом режиме, поле и сетку нарисовать смогу, а как перемещаться поэтой сетке(для выделения острова) и сделать так, чтоб масив заполнялся путем выделения клетки в этой сетке?
@^WARlock^@
7.04.2007 17:03
Так, как можно заполнять массив в графическом режиме?
Lapp
8.04.2007 9:25
Молодец, прога, вроде, работает!
Цитата(@^WARlock^@ @ 7.04.2007 14:03)
как можно заполнять массив в графическом режиме?
Заполнять - точно так же. Нужно поменять только интнрфейс. Я не совсем понимаю, зачем ты сделал юнит ENGINE.. Вот выделить интерфейс в отдельный юнит - это было бы правильно. Тогда замена текста на графику состояла бы в написании нового юнита - и все. Попробуй разделить engine на два юнита, выделив графику. А как писать - аналогично.. Только использовать графику: Line, Rectangle, Bar, OutTextXY.. - и т.д. т.п. . Начни и показывай..
PS а форматирование у тебя все так же на нуле.. Читать такие программы удовольствия мало. Учти, это затрудняет тех, кто отвечает тебе (если уж тебе самому все равно) с соответствующим результатом..
@^WARlock^@
9.04.2007 14:06
Цитата
Попробуй разделить engine на два юнита, выделив графику.
На какие и как? Просто располовинить?
Вот добавил новый юнит GRAFICA, из предыдущих островов. В графическом режиме вылазиет поле, и можно управлять мышью. А как состыковать это все с моей задачей, что-то придумать не могу. Труба полная . Нажмите для просмотра прикрепленного файла
Lapp
9.04.2007 16:38
Цитата(@^WARlock^@ @ 9.04.2007 11:06)
На какие и как? Просто располовинить? ... Труба полная
Попробуй отделить все, что относится к отображению в отдельный юнит. Скажем, твой DrawMap - это явно к отображению, а Schet - нет. Это я грубо, примерно. Остальные найди сам. Соответственно, и переменные разделить. Многое для этого придется переделать, задача сама по себе непростая. А потом по образу и подобию того юнита, который отображает текст, сделаешь юнит, который отображает в графике. Это потребует немалой работы, но зато в результате должно получиться следующее: нужна графика - подставляешь юнит с графикой, нужен текст - подставляешь текстовый..
PS Еще раз поторяю: разберись с форматированием программного текста. Если снова проигнорируешь мой совет - я тоже буду игнорировать твои вопросы. Я не имею в виду, что ты сразу все правильно отфоматируешь, но хотя бы обратить на это внимание - необходимо!
@^WARlock^@
12.04.2007 9:21
Цитата
Еще раз повторяю: разберись с форматированием программного текста. ...
Вот понавтыкал пробелов, может лучше будет.
А вот в этом случае идет заполнение мвссива? Нажмите для просмотра прикрепленного файла Если идет, то я там добавил (Procedure SCHET). Не подскажите, как в графмческом режиме вывести числовую переменную. В данном случае результат процедуры (SCHET).
Lapp
12.04.2007 9:36
Цитата(@^WARlock^@ @ 12.04.2007 6:21)
как в графмческом режиме вывести числовую переменную.
Процедура OutTextXY. Только сначала переведи ее а строку. Прогу гляну чуть позже..
@^WARlock^@
13.04.2007 11:30
В моей последней проге идет хоть какое-то заполнение массива, или нет?
@^WARlock^@
18.04.2007 17:17
Как и "все", я решил забить на подключение графики к моей проге.
Народ, подскажите алгоритм выполнения подсчета островов или блок схему процедуры подсчета островов.
Процедура подсчета островов:
..... 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^@ - чисто по-человечески, скажи, почему ты сначала задаешь вопрос, тебе отвечают, потом ты делаешь все по-другому, а потом снова просишь ответить на вопрос, на который уже отвечено в самом первом посте темы?.. Это вызываает недоумение.. Есть ли смысл говорить, если собеседник не слышит?
@^WARlock^@
22.04.2007 16:58
Цитата
Твоя процедура работает неправильно.
Точно, а я и не замечал(наверное потомучто больше 4-6 островов не выделял). Не подскажите, из-за чего так происходит? И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.
Lapp
23.04.2007 14:35
Цитата(@^WARlock^@ @ 22.04.2007 13:58)
Не подскажите, из-за чего так происходит? И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.
Я тебя решительно не понимаю.. Советов не слушаешь, на вопросы не отвечаешь - я умываю руки..
@^WARlock^@
24.04.2007 9:39
Цитата
Советов не слушаешь, на вопросы не отвечаешь
Советы, по поводу того, что процдура SCHET не корректно работает, я обратил внимание перепроверил, да это действительно так. На какие вопросы я не отвечаю? Мне кажется, что совсем наоборот, мои вопросы ни кто не замечат.
Lapp
24.04.2007 9:57
Цитата(@^WARlock^@ @ 24.04.2007 6:39)
На какие вопросы я не отвечаю?
Вот на этот: @^WARlock^@ - чисто по-человечески, скажи, почему ты сначала задаешь вопрос, тебе отвечают, потом ты делаешь все по-другому, а потом снова просишь ответить на вопрос, на который уже отвечено в самом первом посте темы?.. Это вызываает недоумение.. Есть ли смысл говорить, если собеседник не слышит?
Lapp
24.04.2007 10:18
Цитата(@^WARlock^@ @ 22.04.2007 13:58)
И, что надо изменить в процедуре SCHET, чтобы прога считала правильно.
Мой совет: вернись к началу, и возьми мою процедуру в точности в том виде, в котором она есть. Я понимаю, тебя не устраивает, что в ней острова обозначены -1, а не 1. Поменяй в моей процедуре все знаки на обратные. То есть острова обозначай 1, а их номера - отрицательными числами. Это самый простой способ, имхо.. Тогда и алгоритм будет один в один. Сможешь взять прямо из первого мессаджа. Что непонятно - я объясню..
PS ты извини за наезды, просто старайся внимательно читать советы и придерживаться их. Либо говори, почему делаешь иначе. Ведь это же двусторонний разговор, так?
Добавлено через 4 мин. Но будет значительно красивее, если ты в своей части переделаешь 1 на -1. По-хорошему, вообще не нужно привязываться к конкретному числу. Просто сделай константу - скажем, Terra = -1. При заполнении островов используй ее. Нигде не пользуйся явно минус единицей или единицей. Вот подсчет - это другое дело. Номер должен быть явно. Улавливаешь идею? Говори тут активней, тогда результат будет лучше. Успехов!
@^WARlock^@
27.04.2007 15:02
Не понимаю почему я тупил столько времени. LAPP - видимо всетаки ты отчасти был прав, на счет того, что я не слушаю советов. Например вот этот.
Надеюсь теперь ты мне поможешь реализовать блок-схему процедуры SCHET.
И еще такой нюанс, как сделать, чтобы мой PASCAL распознавал русский язык.
Lapp
27.04.2007 15:43
Цитата(@^WARlock^@ @ 27.04.2007 12:02)
Не понимаю почему я тупил столько времени.
Бывает.. одни тупят, другие ждут у них просветления. Главное - дождаться..
Цитата(@^WARlock^@ @ 27.04.2007 12:02)
видимо всетаки ты отчасти был прав, на счет того, что я не слушаю советов.
Фраза сказана предельно осторожно, но если ты действительно это понял хоть немного - это самое большое твое (и немного мое ) достижение в этой работе. Программирование на втором месте..
Цитата(@^WARlock^@ @ 27.04.2007 12:02)
Надеюсь теперь ты мне поможешь реализовать блок-схему процедуры SCHET.
Помогу обязательно! Только сначала высплюсь..
Цитата(@^WARlock^@ @ 27.04.2007 12:02)
И еще такой нюанс, как сделать, чтобы мой PASCAL распознавал русский язык.
Этот вопрос много раз обсуждался, есть надежные способы. Признаться, я по ним не спец..
@^WARlock^@
2.05.2007 8:23
LAPP - говорил, что поможешь реализовать блок-схему процедуры SCHET, а сам пропал куда-то.
Lapp
2.05.2007 9:01
Цитата(@^WARlock^@ @ 2.05.2007 5:23)
LAPP - говорил, что поможешь реализовать блок-схему процедуры SCHET, а сам пропал куда-то.
А разве ты уже выложил последний рабочий вариант программы?.. Я слежу и каждый день проверяю..
Добавлено через 1 мин. Кроме того, помочь - не значит сделать за тебя. Ты выложи, что сделал (как ты это сделал со старым вариантом), я посмотрю и подправлю.. Ок?
Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов. Может тогда и придумаю, как нарисовать блок-схему.
Lapp
2.05.2007 10:42
Цитата(@^WARlock^@ @ 2.05.2007 7:39)
Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов
Сейчас попробую вспомнить.. Я просто введу комментарии в тот агоритм в первом посте.
Lapp
2.05.2007 12:02
1. Обнуляем счетчик островов N. Ну, это понятно.
2. Проходим по всему массиву до встречи первой -1. Тоже понятно - идем до встречи с нехоженой землей. В самом начале в нашем массиве есть только 0 (вода) и -1 (земля). Затем земля перемаркировывается номером острова. Но -1 всегда означает землю, на которой мы еще не были (где не ступала нога человека ).
3. Если ни одной -1 не было найдено - выходим. И это понятно - неизведанные земли кончились. Выход из процедуры.
4. Увеличиваем N на 1. Если нашли -1 - значит, нашли новый остров. Увеличиваем счетчик островов.
5. Меняем значение найденной клетки на N. Столбим землю. Вместо -1 записываем номер острова
6. Сбрасываем флаг. Флаг будет установлен, если мы найдем новые клетки этого же острова (то есть -1 соседние к N). Он нужен нам, чтобы понять, когда закончится процесс перемаркировки текущего (N-го) острова.
7. Проходим циклом по всему массиву. Если текущий элемент равен -1, а один из его четырех соседей равен N, то меняем его на N и устанавливаем флаг. Цикл по всему массиву - это двойной цикл по координатам, как обычно (по строчкам, сверху вниз). Перемаркировка текущего острова производится не за один цикл. Это я поясню потом на примере
8. Если флаг установлен - переходим к п.6 Установленный флаг означает, что соседние клетки были найдены. А это значит, что могут быть и соседние к новым найденным. Значит, надо пройти еще раз..
9. Если флаг сброшен - переходим к п.2 Сброшенный флаг значит, что за последний проход не было найдено новых соседних клеток к текущему острову. Значит, мы нашли все. Можно переходить к поиску нового острова.
Вот пример. Представь себе остров, закрученный наподобие спирали (# означает -1, а ~ - воду, то есть 0 ):
Пока что сыровато, я не стал вникать. Так в принципе направление верное. В конце есть явная ошибка: выхода в конце нет и быть не может! Выход только в п.4. И почему ты называешь выход "выводом"?..
@^WARlock^@
2.05.2007 15:40
Цитата
Пока что сыровато
Я в блок-схемах не силен. Может тогда предложишь свой вариант.
@^WARlock^@
3.05.2007 9:08
Цитата
И почему ты называешь выход "выводом"?
Как я понял, это выход в твоей проге, а в моей это вывод кол-ва островов, поэтому и "вывод".