HackerRank Java 1D Array (Часть 2)

Question

Я пытаюсь решить следующий вопрос HackerRank Java 1D Array

Я пришел со следующим обратного прослеживания подхода.

import java.util.Scanner; 

public class Solution { 
static int arr[]; 

public static void main(String[] args) {  
    Scanner sc= new Scanner(System.in); 
    int T = sc.nextInt(); 
    for (int j= 0; j < T; j++) { 
     int n = sc.nextInt(); 
     arr = new int[n]; 
     int m = sc.nextInt(); 
     for (int k = 0; k< n; k++) { 
      arr[k]= sc.nextInt(); 
     } 
     if(canReach(0,arr.length,m)) 
      System.out.println("YES"); 
     else 
      System.out.println("NO"); 
    } 
} 
public static boolean canReach(int src,int dest,int m) 
{ 
    if(src>=(dest-1)||(src+m)>=dest) 
     return true; 
    if(isValidDest(src+1)&&canReach(src+1, dest, m)) 
     return true; 
    if(isValidDest(src-1)&&canReach(src-1, dest, m)) 
     return true; 
    if(isValidDest(src+m)&&canReach(src+m, dest, m)) 
     return true; 
    return false; 
} 
private static boolean isValidDest(int dest) { 
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0))) 
     return true; 
    return false; 
} 

}

Но я получаю ошибку стека переполнения для следующего теста 0 0 1 1 1 0.

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

Modified code (solution) 

import java.util.Scanner; 

public class Solution { 
static int arr[]; 
static boolean isDestVisited[]; 

public static void main(String[] args) {  
    Scanner sc= new Scanner(System.in); 
    int T = sc.nextInt(); 
    for (int j= 0; j < T; j++) { 
     int n = sc.nextInt(); 
     arr = new int[n]; 
     isDestVisited = new boolean[n]; 
     int m = sc.nextInt(); 
     for (int k = 0; k< n; k++) { 
      arr[k]= sc.nextInt(); 
     } 
     if(canReach(0,arr.length,m)) 
      System.out.println("YES"); 
     else 
      System.out.println("NO"); 
    } 
} 
public static boolean canReach(int src,int dest,int m) 
{ 
    if(src>=(dest-1)||(src+m)>=dest) 
     return true; 
    if(isDestVisited[src]==true) 
     return false; 
    isDestVisited[src]=true; 
    if(isValidDest(src+1)&&canReach(src+1, dest, m)) 
     return true; 
    if(isValidDest(src-1)&&canReach(src-1, dest, m)) 
     return true; 
    if(isValidDest(src+m)&&canReach(src+m, dest, m)) 
     return true; 
    isDestVisited[src]=false; 
    return false; 
} 
private static boolean isValidDest(int dest) { 
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0))) 
     return true; 
    return false; 
} 

}

Answer 1

В рекурсивном алгоритме вы должны избегать обработки одного государства дважды

if (src >= dest) 
    return true; 
if (thisPositionAlreadyTested[src]) 
    return false; 
thisPositionAlreadyTested[src] = true; 
if (... 

или вы можете использовать обр [] содержание для той же цели, если вы можете изменить его