Острова Опции

[@^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]

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

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

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

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

[T i m e]

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

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

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

[TarasBer]

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

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

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

[T i m e]

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

Я отвечал не на исходный вопрос, а на тот который и указал в цитате выше по поводу перемещения по полю.

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

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

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

[Lapp]

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

И еще, поясни, пожалуйста, слова:

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

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

[@^WARlock^@]

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

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

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


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

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

Сообщение отредактировано: @^WARlock^@ - 25.03.2007 12:41

[volvo]

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

[TarasBer]

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

И еще, поясни, пожалуйста, слова:

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

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

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

[@^WARlock^@]

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

Но всетаки:

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

Сообщение отредактировано: @^WARlock^@ - 25.03.2007 12:42

[Lapp]

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

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

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

Поле-то готовое, но только ты выкинул часть, где расставляются корабли (в твоем случае - острова, как я понял). Нажатие мышки в этой программе соответствует выстрелу, после чего проверяется попадание. У тебя же, поскольку массив не заполнен, никакого попадания нет.

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

Для начала - введи заполнение массива. Если хочешь делать это мышью - значит просто ставь 1 в соответствующий элемент массива ac. И убери проверку на попадание...
Подсчет островов - это будет просто двойной цикл суммирования:

s:=0;
for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];

Ты это хотел? У меня все меньше уверенности, что я тебя правильно понимаю..
И хотя бы намекни, что же ты хочешь иметь в конце. Просто посчитать острова?..

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

TarasBer, это все слова. Предложи конкретный алгоритм, если уж говоришь о нем. А зоадно скажи, чем тебе не по нраву тот, который я привел в первом ответе.

[@^WARlock^@]

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

Да просто подсчитать острова, их кол-во должно отображаться на экране.

[@^WARlock^@]

Эот код действителен если остров состоит из одной клетки.

Код

s:=0;
for j:=1 to 10 do for i:=1 to 10 do s:=s+ac[i,j];

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

Сообщение отредактировано: @^WARlock^@ - 27.03.2007 11:17

[Lapp]

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

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

[@^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

 OSTROVA.rar ( 9.15 килобайт ) Кол-во скачиваний: 395


Сообщение отредактировано: @^WARlock^@ - 28.03.2007 4:32