Помогите с алгоритмом

← →
brother © (2012-08-30 07:46) [0]

Есть двухмерный массив значений: http://brotherirk.narod.ru/untitled.PNG
Нужен алгоритм который получит координаты красных квадратов (но не желтых).
Начало отсчета обозначено зеленым.
Думал обходить все красные квадраты по часовой стрелке до замкнутого контура, но тогда голубые квадраты будут не включены в список(
Как бы лучше это реализовать?

← →
MBo © (2012-08-30 08:31) [1]

На текущем уровне постановки задачи:
Обойти всё.
Если квадрат красный, а еще хлеще - голубой, то добавить в список.

← →
brother © (2012-08-30 08:34) [2]

если идти по часовой стрелке, то по голубым квадратам мы никогда не пройдем( тк идем всегда по краю...

← →
brother © (2012-08-30 08:36) [3]

> Обойти всё.

каким алгоритмом обходить?

← →
MBo © (2012-08-30 08:40) [4]

Задачу опиши нормально

← →
Алгоритм (2012-08-30 08:45) [5]

Нужен алгоритм который получит координаты красных квадратов
Задача поставлена не четко.
Причем здесь "но не желтых", голубые?
обойти все скорее всего означает

for i:= to ...
for j:= to ...
if Красный then

где-то так

← →
brother © (2012-08-30 08:47) [6]

это доска на ней есть зоны. нужно по клику в определенном месте найти все зоны прилегающие к месту клика.
В данном примере, есть 2 зоны: красная, желтая и белая(пустота). Красная зона имеет замкнутый контур, вот нужно получить координаты всех красных квадратов образующих этот контур...
Зеленый, голубой квадраты, также являются красными и входят в этот контур (я их выделил другим цветом, чтобы Вам видно было о каких проблеммах я говорю).

← →
MBo © (2012-08-30 08:50) [7]

Похоже на то, что тебе нужен 4-связный алгоритм flood fill

← →
brother © (2012-08-30 08:52) [8]

еще точнее: красные квадраты в таком расположении создают замкнутый контур, необходимо взять за точку отсчета зеленый квадрат (он же красный просто я его показываю зеленым для наглядности) и обойти все красные квадраты получая их координаты. проблемма в том, что если по контуру обходить, то вот в голубые (они же тоже красные) мы никогда не попадем...

← →
brother © (2012-08-30 08:56) [9]

> тебе нужен 4-связный алгоритм flood fill

посмотрю...

← →
Труп Васи Доброго © (2012-08-30 09:34) [10]

А почему нельзя проверить все соседние (от кликнутого квадрата) на "красность/голубизну" (хоть по часовой стрелке, хоть против)? Каждый проверенный квадрат заносишь в "проверенный" массив. Если сосед красный, то записать его координаты в "красный" массив. Дальше типа рекурсия для каждого найденного красного квадрата повторить весь алгоритм, исключая из проверки квадраты из "проверенного" массива и так до тех пор, пока не останется не проверенных.
Это так первое что в голову пришло, но работать будет.

← →
brother © (2012-08-30 10:07) [11]

алгоритм flood fill это оно, что было нужно.

← →
Труп Васи Доброго © (2012-08-30 14:14) [12]

Исходя из условий - flood fill нифига не то. Ты же ничего не flood, ты только ищешь, а значит не изменяешь характеристику квадрата, а без изменения характеристики алгоритм flood fill зациклится. Мой вариант, или подобный с дополнительным массивом, сработает.

← →
brother © (2012-09-01 08:31) [13]

> Ты же ничего не flood,

на самом деле, после поиска все это меняет цвет на бклый...

← →
Sha © (2012-09-01 10:07) [14]

красный квадрат - что это в исходной задаче?

← →
brother © (2012-09-01 13:26) [15]

byte в 2хмерном массиве... означает id объекта на поле... если id одного типа задают область, это и надо узнать...

← →
Sha © (2012-09-01 13:40) [16]

Эти id ведь как-то в этом массиве появились.

Вот когда они там появлялись, их координаты и надо было связать в список.

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

← →
brother © (2012-09-01 13:50) [17]

даже если я буду иметь координаты, как то же надо узнать, кто группируясь создает область примыкающих однотипных объектов...

← →
brother © (2012-09-01 13:54) [18]

подобная задача: http://brotherirk.narod.ru/untitled2.PNG
как узнать какие квадраты открыть при клике в зеленом квадрате?

← →
Sha © (2012-09-01 13:59) [19]

так ты сапера ваяешь? там очевидно же все

← →
Sha © (2012-09-01 14:19) [20]

каждая клетка - байт в двумерном массиве
младший нибл - счетчик бомб
в старшем - наличие бомбы, наличие флага, видимость

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

← →
brother © (2012-09-01 15:46) [21]

> так ты сапера ваяешь?

нет, но похожая задача...

← →
brother © (2012-09-01 15:50) [22]

тренерую мозг алгоритмами, игра: http://brotherirk.narod.ru/untitled3.PNG

← →
Sha © (2012-09-01 16:04) [23]

по картинке не понять, что там надо сделать

← →
brother © (2012-09-01 16:06) [24]

кликать по камешкам одинкаового цвета (группирующихся не менее чем 2...) и они будут убираться...

← →
brother © (2012-09-01 16:14) [25]

перезалил http://brotherirk.narod.ru/untitled3.PNG
если кликнуть по любому камешку из группы (группу выделил красным) они все удаляться и верхние камешки упадут до заполнения...
вообще я уже сабж решил, но если интересно, позже, могу скинуть работающий пример...

← →
Sha © (2012-09-01 18:33) [26]

1 чистим список 2 добавляем кликнутый камень в список без отметок 3 в цикле для каждого камня из списка 3а если нет отметки, что через камень провели вертикаль, то ставим эту отметку и добавляем в список подходящие камни на той же вертикали (с вертикальной отметкой) 3б если нет отметки, что через камень провели горизонталь, то ставим эту отметку и добавляем в список подходящие камни на той же горизонтали (с горизонтальной отметкой) 4 по окончании работы цикла все камни должны иметь обе отметки, осталось сравнить число камней в списке с минимумом и удалить группу, если это число больше

← →
brother © (2012-09-01 19:36) [27]

не совсем понял 3а и 3б, видимо вечереет) если накидаешь код, будет более понятно наверное...

> brother

http://en.wikipedia.org/wiki/Connected-component_labeling

спс, посомтрю, может заменю с flood fill на него...

например, так (на форму брось StringGrid, уменьши размер ячеек и кликай):

const xSize= 10; ySize= 20; zSize= xSize * ySize; var Stone: array[0..zSize-1] of byte; procedure TForm1.FormCreate(Sender: TObject); var x, y, z: integer; begin; Randomize; for z:=0 to zSize-1 do Stone[z]:=Random(7)+1; //один из 7 цветов StringGrid1.ColCount:=xSize; StringGrid1.RowCount:=ySize; for x:=0 to xSize-1 do for y:=0 to ySize-1 do StringGrid1.Cells[x,y]:=IntToStr(Stone[y*xSize+x]); end; procedure TForm1.StringGrid1Click(Sender: TObject); const xMark= $40000000; yMark= $20000000; var x, y, z, zz, t, count, last: integer; Mark: array[0..zSize-1] of integer; begin; x:=StringGrid1.Col; y:=StringGrid1.Row; z:=y*xSize+x; if (x<0) or (x>=xSize) or (y<0) or (y>=ySize) or (Stone[z]=0) then exit; for t:=0 to zSize-1 do Mark[t]:=0; last:=z; count:=0; repeat; if Mark[z] and xMark=0 then begin; zz:=z; for t:=z mod xSize + 1 to xSize-1 do begin; inc(zz); if Stone[z]=Stone[zz] then begin; Mark[last]:=Mark[last]+zz; last:=zz; Mark[last]:=Mark[last] or xMark; end else break; end; zz:=z; for t:=z mod xSize - 1 downto 0 do begin; dec(zz); if Stone[z]=Stone[zz] then begin; Mark[last]:=Mark[last]+zz; last:=zz; Mark[last]:=Mark[last] or xMark; end else break; end; end; if Mark[z] and yMark=0 then begin; zz:=z; for t:=z div xSize + 1 to ySize-1 do begin; inc(zz, xSize); if Stone[z]=Stone[zz] then begin; Mark[last]:=Mark[last]+zz; last:=zz; Mark[last]:=Mark[last] or yMark; end else break; end; zz:=z; for t:=z div xSize - 1 downto 0 do begin; dec(zz, xSize); if Stone[z]=Stone[zz] then begin; Mark[last]:=Mark[last]+zz; last:=zz; Mark[last]:=Mark[last] or yMark; end else break; end; end; inc(count); zz:=z; z:=Mark[z] and not (xMark or yMark); until zz=last; if count>=3 then begin; z:=y*xSize+x; repeat; Stone[z]:=0; zz:=z; z:=Mark[z] and not (xMark or yMark); until zz=last; for x:=0 to xSize-1 do for y:=0 to ySize-1 do if Stone[y*xSize+x]=0 then StringGrid1.Cells[x,y]:="" else StringGrid1.Cells[x,y]:=IntToStr(Stone[y*xSize+x]); end; end;

забыл запретить повторное включение в список, исправил:
const xSize= 10; ySize= 20; zSize= xSize * ySize; var Stone: array[0..zSize-1] of byte; procedure TForm1.FormCreate(Sender: TObject); var x, y, z: integer; begin; Randomize; for z:=0 to zSize-1 do Stone[z]:=Random(7)+1; //один из 7 цветов StringGrid1.ColCount:=xSize; StringGrid1.RowCount:=ySize; for x:=0 to xSize-1 do for y:=0 to ySize-1 do StringGrid1.Cells[x,y]:=IntToStr(Stone[y*xSize+x]); end; procedure TForm1.StringGrid1Click(Sender: TObject); const xMark= $40000000; yMark= $20000000; var x, y, z, zz, t, count, last: integer; Mark: array[0..zSize-1] of integer; begin; x:=StringGrid1.Col; y:=StringGrid1.Row; z:=y*xSize+x; if (x<0) or (x>=xSize) or (y<0) or (y>=ySize) or (Stone[z]=0) then exit; for t:=0 to zSize-1 do Mark[t]:=0; last:=z; count:=0; repeat; if Mark[z] and xMark=0 then begin; Mark[z]:=Mark[z] or xMark; zz:=z; for t:=z mod xSize + 1 to xSize-1 do begin; inc(zz); if Stone[z]=Stone[zz] then begin; if Mark[zz] and (xMark or yMark)=0 then begin; Mark[last]:=Mark[last]+zz; last:=zz; end; Mark[zz]:=Mark[zz] or xMark; end else break; end; zz:=z; for t:=z mod xSize - 1 downto 0 do begin; dec(zz); if Stone[z]=Stone[zz] then begin; if Mark[zz] and (xMark or yMark)=0 then begin; Mark[last]:=Mark[last]+zz; last:=zz; end; Mark[zz]:=Mark[zz] or xMark; end else break; end; end; if Mark[z] and yMark=0 then begin; Mark[z]:=Mark[z] or yMark; zz:=z; for t:=z div xSize + 1 to ySize-1 do begin; inc(zz, xSize); if Stone[z]=Stone[zz] then begin; if Mark[zz] and (xMark or yMark)=0 then begin; Mark[last]:=Mark[last]+zz; last:=zz; end; Mark[zz]:=Mark[zz] or yMark; end else break; end; zz:=z; for t:=z div xSize - 1 downto 0 do begin; dec(zz, xSize); if Stone[z]=Stone[zz] then begin; if Mark[zz] and (xMark or yMark)=0 then begin; Mark[last]:=Mark[last]+zz; last:=zz; end; Mark[zz]:=Mark[zz] or yMark; end else break; end; end; inc(count); zz:=z; z:=Mark[z] and not (xMark or yMark); until zz=last; if count>=3 then begin; z:=y*xSize+x; repeat; Stone[z]:=0; zz:=z; z:=Mark[z] and not (xMark or yMark); until zz=last; for x:=0 to xSize-1 do for y:=0 to ySize-1 do if Stone[y*xSize+x]=0 then StringGrid1.Cells[x,y]:="" else StringGrid1.Cells[x,y]:=IntToStr(Stone[y*xSize+x]); end; end;

интересно, но мой алгоритм flood fill быстрее будет?:
function TScene.FloodFill_(X, Y: integer; AJewels: TTJewel): integer; // aica?auaao eiee?anoai oaaeaiiuo oi?ae var LeftX, RightX, Color : Integer; begin result:= 0; Color:= AJewels[X, Y].ID; AJewels[X, Y].ID:= 0; Inc(Result); RightX:= X + 1; while (RightX <= high(AJewels)) AND (AJewels[RightX,Y].ID = Color) do begin AJewels[RightX, Y].ID:= 0; Inc(result); Inc(RightX); end; LeftX:= X - 1; while (LeftX >= 0) AND (AJewels[LeftX,Y].ID = Color) do begin AJewels[LeftX, Y].ID:= 0; Inc(result); Dec(LeftX); end; if Y >= 1 then begin X:= LeftX + 1; while X < RightX do begin if AJewels[X, Y-1].ID = Color then Inc(result, FloodFill_(X, Y-1, AJewels)); Inc(X); end; end; if Y < high(AJewels[0]) then begin X:= LeftX + 1; while X < RightX do begin if AJewels[X, Y+1].ID = Color then Inc(Result, FloodFill_(X, Y+1, AJewels)); Inc(X); end; end; end;

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

оптимизируй(лучше под битмап), завтра на битмапах сравним)

В первоначальной постановке задачи требовалось выполнить подсчет,
а не банально вызвать FloodFill.

В той игре, которую ты привел http://brotherirk.narod.ru/untitled3.PNG
может возникнуть ситуация, когда после подсчета соседних камней
выяснится, что цвет менять не надо. Причем тут FloodFill?
Но его, конечно, можно доделать для подсчета квадратов.

Так что, доделай, и можно будет посоревноваться.

Свой алгоритм я привел, только для того, чтобы пояснить идею такой доработки.
Фактически, это немного доработанный FloodFill, который составляет список.

> brother

И еще так и не ясно, нужен тебе список или нет?

пока с алгоритмами разбирался отказался от ссписка координат, достаточно возвратить сколько квадратов удалил флууд филл ;)

в твоем алгоритме внутренние точки, которые изменят свой цвет, проверяются трижды

Помогите с алгоритмом Найти похожие ветки