Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];

Вниз

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

 
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б, видимо вечереет) если накидаешь код, будет более понятно наверное...


 
DVM ©   (2012-09-01 20:21) [28]


> brother ©

Алгоритм ищи по словосочетанию "Connected components"


 
DVM ©   (2012-09-01 20:23) [29]


>  brother

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


 
brother ©   (2012-09-01 20:26) [30]

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


 
Sha ©   (2012-09-01 22:10) [31]

например, так (на форму брось 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;


 
Sha ©   (2012-09-01 22:31) [32]

забыл запретить повторное включение в список, исправил:

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;


 
brother ©   (2012-09-01 22:55) [33]

интересно, но мой алгоритм 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;



 
Sha ©   (2012-09-01 23:22) [34]

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


 
brother ©   (2012-09-01 23:24) [35]

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


 
Sha ©   (2012-09-01 23:55) [36]

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

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

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

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


 
Sha ©   (2012-09-02 02:44) [37]

> brother

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


 
brother ©   (2012-09-02 07:54) [38]

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


 
Sha ©   (2012-09-02 12:48) [39]

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



Страницы: 1 вся ветка

Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.56 MB
Время: 0.093 c
15-1337084520
Max
2012-05-15 16:22
2013.03.22
аналог AsProtect


15-1344315493
картман
2012-08-07 08:58
2013.03.22
резюме


15-1340224203
Юрий
2012-06-21 00:30
2013.03.22
С днем рождения ! 21 июня 2012 четверг


6-1233066271
Usov
2009-01-27 17:24
2013.03.22
Как можно реализовать многосекционную закачку файла по http?


2-1338540050
rioko
2012-06-01 12:40
2013.03.22
Закрашивание ячейки стрингрида если над ячейкой находится объект





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский