Первый поиск по сетке 8x8 в Java

Question

То, что я пытаюсь сделать, - подсчитать, сколько ходов требуется для достижения цели с использованием кратчайшего пути. Это нужно сделать, используя первый поиск по ширине. Я поместил сетку 8x8 в 2d-массив, который заполнен одним из четырех символов, E для пустого (может перемещаться в эти пятна), B для заблокированных (не может двигаться здесь), R для робота (начальная точка) или G для цели. Алгоритм должен был проверять подвижные пробелы в порядке вверх, влево, вправо, затем вниз, что, я считаю, я сделал правильно. После проверки узла он изменяет свое содержимое на «B». Если цель не может быть достигнута, 0 следует вернуть.

Я изменил свой код, чтобы реализовать то, что сказал мне Kshitij, и он прекрасно работает. Я просто слишком устал, чтобы убедиться, что я не инициализировал свою очередь после каждого нового набора данных lol. Спасибо за помощь!

public static int bfSearch(){ 
    Queue <int []> queue = new LinkedList <int []>(); 
    int [] start = {roboty,robotx,0}; 
    queue.add(start); 

    while (queue.peek() != null){ 
     int [] array = queue.remove(); 

      if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){ 

       if (grid[array[0]-1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]-1][array[1]] = 'B'; 
        int [] temp = {array[0]-1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){ 

       if (grid[array[0]][array[1]-1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]-1] = 'B'; 
        int [] temp = {array[0], array[1]-1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){ 

       if (grid[array[0]][array[1]+1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]+1] = 'B'; 
        int [] temp = {array[0], array[1]+1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){ 

       if (grid[array[0]+1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]+1][array[1]] = 'B'; 
        int [] temp = {array[0]+1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 
     }   
    return 0; 
} 

Answer 1

Вам нужно будет хранить 2 вещи в очереди. Давайте назовем каждый элемент в вашей очереди узлом.

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

Вы начинаете путем присвоения счета вашей начальной позиции 0.

путь алгоритм работы является:

1. вы совать узел из очереди
2. вы определяете, где вы можете перейти от позиции, указанной узлом, который вы только что нажали. То есть, если вы рассматриваете это как «создание дерева на лету», вы определяете детей узла, который вы выскочили из очереди.
3. вы добавляете этих детей в очередь.

На третьем шаге, когда вы добавляете дочерний узел в очередь, вам нужно будет определить счетчик, который необходимо добавить в этот узел. Этот счет просто равен count of the parent node (that you popped in step 1) + 1

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

Например, позволяет работать с сеткой 4x4, где позиция [0,0] - это начало, а позиция [0,3] - пункт назначения.

S E E B 
E B E E 
B B B E 
G E E E 

Первоначально, ваша очередь будет:

[{(0, 0), 0}] 

где значение внутри () является положение, а второе значение внутри {} является счетчиком.

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

[{(0, 1), 1}, {(1, 0), 1}] 

Вы выскочить первый элемент, понимают, что это не имеет жизнеспособных детей, так вы двигаетесь дальше.

Вы выталкиваете оставшийся элемент и узнаете, что он дает вам один узел, к которому вы можете добраться, в позиции (2, 0). Поскольку у вас выбранный узел имеет счет 1, вы добавляете эту новую позицию в паре с count = 1 + 1 = 2 в очередь.

В конце концов, вы будете совать узел цели из очереди, и это счетчик будет 9.

Редактировать

Если вы хотите, чтобы получить путь от источника к месту назначения, текущая кодировка не работает как есть. Вам нужно будет поддерживать отдельный 2D-массив размером 8x8 с подсчетами вместо их кодирования в самом узле. И когда вы, наконец, найдете счетчик для пункта назначения, вы возвращаетесь из пункта назначения в источник, используя массив 2D-счетчиков. По сути, если вы можете добраться до места назначения за 9 ходов, вы можете добраться до одного из своих смежных позиций за 8 ходов. Таким образом, вы находите позицию, которая имеет счет 8 и находится рядом с пунктом назначения. Вы итеративно повторяете это, пока не дойдете до источника.

Метод, который вы описали, где вы добавляете дополнительный элемент к узлам, не работает. Я оставлю это для вас, чтобы узнать, почему, так как это домашнее задание :)

Answer 2

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

Я прокомментировал объяснение настолько, насколько мог. Он читается даже для людей, которые не имеют ни малейшего представления. Мне довелось встретить ваш вопрос, когда я реализовал решение для аналогичной (той же?) Проблемы, когда парень, оказавшийся в лабиринте, должен был найти выход. В сетке были ловушки (B) и подвижные области (E). Цель состояла в том, чтобы добраться до места назначения (G).

В любом случае, вот обобщенный код. Я принимаю no строк, столбцов, а затем полную сетку. Я только печатаю, можно ли выполнить REACH в пункт назначения или нет. Я оставляю остальное Шифрование до кого-то, кто читает это упражнение, чтобы убедиться, что вы поняли код;)

виду тот факт, что главная цель мой ответ, чтобы показать вам, что размер вашего BFS функция может быть уменьшена. Я публикую все свое решение, чтобы дать общее представление о BFS, примененном в сетке, так как я боролся, изучая его. Надеюсь, это поможет кому-то застрять в той же ситуации. Если вы хотите, чтобы положение или путь следовали или что-то еще, следуйте инструкциям из ответов в этом вопросе. Сделай сам;)

import java.util.*; 

/** 
* Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA 
*/ 

class MAZE 
{ 
    static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates 
    static int[] dx={1,-1,0,0};//right, left, NA, NA 
    static int[] dy={0,0,1,-1};//NA, NA, bottom, top 
    static char[][] grid;//Main grid 
    public static void main(String[] args) 
    { 
     Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice 
     r=sc.nextInt(); 
     c=sc.nextInt(); 
     grid=new char[r][c]; 
     for(int i=0;i<r;i++) 
     { 
      char[] s1=sc.next().toCharArray();//Reading a line of the Grid 
      System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually 
     } 
     s1=sc.nextInt()-1; 
     s2=sc.nextInt()-1; 
     f1=sc.nextInt()-1; 
     f2=sc.nextInt()-1; 
     if(MAZEBFS()) 
     { 
      System.out.println("PATH EXISTS"); 
     } 
     else 
     { 
      System.out.println("PATH DOES NOT EXIST"); 
     } 
    } 
    private static boolean MAZEBFS() 
    { 
     if(s1==f1&&s2==f2) 
     { 
      return true;//He's already there 
     } 
     else 
     { 
      grid [f1][f2]='G';//finish 
      Queue<int[]> q=new LinkedList<int[]>(); 
      int[]start={s1,s2};//Start Coordinates 
      q.add(start);//Adding start to the queue since we're already visiting it 
      grid[s1][s2]='B'; 
      while(q.peek()!=null) 
      { 
       int[]curr=q.poll();//poll or remove. Same thing 
       for(int i=0;i<4;i++)//for each direction 
       { 
        if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c)) 
        { 
         //Checked if x and y are correct. ALL IN 1 GO 
         int xc=curr[0]+dx[i];//Setting current x coordinate 
         int yc=curr[1]+dy[i];//Setting current y coordinate 
         if(grid[xc][yc]=='G')//Destination found 
         { 
          //System.out.println(xc+" "+yc); 
          return true; 
         } 
         else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now 
         { 
          //System.out.println(xc+" "+yc); 
          grid[xc][yc]='B';//now BLOCKED 
          int[]temp={xc,yc}; 
          q.add(temp);//Adding current coordinates to the queue 
         } 
        } 
       } 
      } 
      return false;//Will return false if no route possible 
     } 
    } 
} 

Код в действии: http://ideone.com/jiZKzn

Любые предложения приветствуются. Cheers: D