поведение стека вызовов при рекурсии

 
0
 
Java
ava
TassadarStv | 27.03.2013, 18:15

Хочу написать программу для игры в ГО, на данный момент требуется написать функцию которая получив на входе координаты камня находит все камни принадлежащие к этой группе и записывает их в group. Group это список массивов byte[3], каждый массив - это камень, byte[0] - это цвет камня(1 - черный камень,  2 - белый камень, 0 - пустая позиция на доске).  Игровая доска представляет из себя массив 19x19, каждый элемент массива это позиция на доске куда можно поставить камень, черный или белый. Тестовая доска выглядит так

Goban[0]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[1]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[2]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[3]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[4]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[5]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[6]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[7]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[8]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[9]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[10]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[11]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[12]= new byte[]{0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0};
Goban[13]= new byte[]{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0};
Goban[14]= new byte[]{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0};
Goban[15]= new byte[]{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0};
Goban[16]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[17]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Goban[18]= new byte[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};    

   Тут мы имеем группу из 21го черного камня, функция записывающая все камни в группе выглядит так:

private ArrayList<byte[]> groupStonesFinder(int x, int y, int color, ArrayList<byte[]> group){
            byte[] stone = new byte[3];
            stone[0] = (byte)(color);
            stone[1] = (byte)(x);
            stone[2] = (byte)(y);
            group.add(stone);
                if((y+1)<=18){if((Goban[x][y+1]==color)&(!this.alreadyInGroup(x,y+1,group))){
                    y = y + 1;
                    groupStonesFinder(x,y,color,group);
                }}
                if((x-1)>=0){if((Goban[x-1][y]==color)&(!this.alreadyInGroup(x-1,y,group))){
                    x = x - 1;
                    groupStonesFinder(x,y,color,group);                
                }}
                if((x+1)<=18){if((Goban[x+1][y]==color)&(!this.alreadyInGroup(x+1,y,group))){
                    x = x + 1;
                    groupStonesFinder(x,y,color,group);
                }}
                if((y-1)>=0){if((Goban[x][y-1]==color)&(!this.alreadyInGroup(x,y-1,group))){
                    y = y - 1;
                    groupStonesFinder(x,y,color,group);
                }}
                
            return group;
        }

//Метод alreadyInGroup, проверяте наличие камня в данной группе
            private static boolean alreadyInGroup(int x, int y, ArrayList<byte[]> group){
                for(int i=0;i<=group.size()-1;i++){
                    if((group.get(i)[1]==(byte)(x))&(group.get(i)[2]==(byte)(y))){
                        return true;
                    }
                }
                return false;
            }




  данный метод работает сейчас следующим образом, получив координаты первого камня x = 12, y=7, color = 1, первый камень сразу же записывается в group, потом метод проверяет наличие соседей(слева, справа, снизу и сверху) у этого камня, и если сосед еще не внесен в список группы, то мы вызываем метод рекурсивно, передавая ему координаты этого соседа. Таким образом в объекте group должно быть по завершению выполнения метода 21 камень. В действительности же получается всего 3 камня в группе.
Метод сейчас работает так:
- получив камень(12,7) он записывает его в group, потом смотрит соседа с права, сосед справа есть и он еще не внесен в список, запускаем метод снова передав ему координаты соседа справа;
- заносим это камень в group, снова смотрим соседа справа, переходим к соседу справа
- заносим камень в список, смотрим соседа справа, его нет, потом других соседей сверху нет, снизу нет, слева есть но к нему не идем, так как он уже внесен в список и тут данная ветка рекурсии прекращается, и по моему соображению, должна вернуться к тому месту где мы вызывали метод первый раз и должна проверять уже других соседей, сверху, снизу и т.д., но этого не происходит, рекурсия прекращается полностью.
  И как тут быть? Как сделать, что бы программа возвращалась к первому вызову и продолжала свою работу,
   
        
Ответы (1)
ava
TassadarStv | 27.03.2013, 22:33 #
Щас свой алгоритм перечитал и понял что фигню написал, модераторам просьба снести тему 
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить