Я не могу изменить мою статическую переменную в java

Question

Вы даете сетку (здесь 4x4). вам нужно узнать общее количество уникальных путей от (0,0) до (4,4). main() вызывает функцию для этого. Он находит возможные «следующие шаги» и называет это снова. Когда (4,4) достигнуто noOfPaths ++; должен выполняться. Этого не происходит, и я не могу найти проблему.

import java.util.ArrayList; 

    public class NoOfPaths { 
     static int xRows = 4; 
     static int yColumns = 4; 
     static int noOfPaths = 0; 

     /*A robot is located in the upper-left corner of a 4×4 grid. 
     * The robot can move either up, down, left, or right, 
     * but cannot go to the same location twice. 
     * The robot is trying to reach the lower-right corner of the grid. 
     * Your task is to find out the number of unique ways to reach the destination. 
     **/ 

     static ArrayList validNeighbours (int x,int y, ArrayList visited) { 
      ArrayList valid = new ArrayList(); 

      if((x+1 <= xRows) && !visited.contains(((x+1)*10)+y)) { 
       valid.add(((x+1)*10)+y); 
      } 
      if((x-1 >= 0) && !visited.contains(((x-1)*10)+y)) { 
       valid.add(((x-1)*10)+y); 
      } 
      if((y+1 <= yColumns) && !visited.contains(x*10+y+1)) { 
       valid.add(x*10+y+1); 
      } 
      if((y-1 >= 0) && !visited.contains(x*10+y-1)) { 
       valid.add(x*10+y-1); 
      } 

      return valid; 
     } 

     static void pathify(int x,int y, ArrayList alreadyVisited) { 
      if(x == xRows && y == yColumns) { 
       noOfPaths++; 
      } else { 
       alreadyVisited.add(x*10+y); 
       ArrayList callAgain = new ArrayList(); 
       callAgain = validNeighbours(x,y,alreadyVisited); 
       for (int t=0,temp; t<callAgain.size(); t++) { 
        temp=(int) callAgain.get(t); 
        pathify(temp/10, temp%10, alreadyVisited); 
       } 

      } 
     } 

     public static void main(String[] args) { 


      ArrayList alreadyVisited = new ArrayList(); 

      pathify(0, 0, alreadyVisited); 

      System.out.println(noOfPaths); 
     } 

    } 

Answer 1

Ошибка в том, как вы обработки alreadyVisited. В первый раз вызывается pathify, этот список будет содержать только начальный квадрат (0,0), что отлично. Вот важная часть вашего кода:

  for (int t=0,temp; t<callAgain.size(); t++) { 
       temp=(int) callAgain.get(t); 
       pathify(temp/10, temp%10, alreadyVisited); 
      } 

Вы нашли соседей исходной ячейки. Ваш код выберет первого соседа; то он найдет пути, начинающиеся с этого соседа, а рекурсивные вызовы pathify добавят ячейки в alreadyVisited.

Теперь, после того, как все рекурсивные вызовы возвращаются, вы готовы найти ячейки, начиная с второй соседом начальной ячейки. Но у вас есть проблема: у alreadyVisited все еще есть все ячейки, которые он собирает с тех путей, которые он нашел, начиная со второго соседа. Итак, вы не найдете все возможные пути, начиная со второго соседа; вы не найдете пути, который включает любой ячейку в любой путь, который вы ранее обнаружили. Это не то, что вы хотите, так как вы хотите избежать посещения одной и той же ячейки в каждый путь - вы не хотите, чтобы вы не посещали одну и ту же ячейку во всех своих предыдущих путях. (Я немного упростил это. На самом деле проблема начнет происходить глубже по рекурсивному стеку, и вы даже не найдете все пути, начинающиеся с первого соседа.)

При реализации рекурсивного алгоритма I «Было обнаружено, что обычно сложно создать промежуточную структуру данных, которая разделяется рекурсивными вызовами, которые будут изменены этими вызовами. В этом случае это список alreadyVisited. Проблема заключается в том, что при более глубоком обращении к стеку, который модифицирует структуру, это влияет на последующие вызовы, поскольку они будут видеть изменения после возвращения более глубоких запросов, которые в основном являются данными, которые им нужно изменить под ними. (Я не говорю о коллекции, которая используется для хранения списка результатов, если список в основном предназначен для записи.) Способ избежать этого заключается в том, что вместо добавления в alreadyVisited вы можете создать клон из этого списка, а затем добавить к нему. Таким образом, более глубокий вызов может быть уверен, что он не влияет на более мелкие вызовы, изменяя их данные. То есть, вместо того, чтобы

alreadyVisited.add(x*10+y); 

записи

alreadyVisited = [make a copy of alreadyVisited]; 
alreadyVisited.add(x*10+y); 

add изменит новый список, а не список, что другие вызовы используют. (Лично я объявляю новую переменную, такую ​​как newAlreadyVisited, так как мне не очень нравятся модификационные параметры для удобства чтения.)

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

EDIT: Я проверил его, и он, кажется, работает: 12, если xRows = yColumns = 2, 8512, если оба 4 (это правильно?). Другой подход: вместо копирования списка, я попытался

alreadyVisited.remove((Object)(x*10+y)); 

в конце метода ((Object) требуется, так что Java не думает, что вы удаляете с индексом), и это дало мне те же результаты , Если вы это сделаете, вы убедитесь, что alreadyVisited - это то же самое, когда pathify возвращается, как только оно начиналось. Но я хочу подчеркнуть, что я не рекомендую этот подход «очистки», если вы действительно не знаете, что делаете.