Advertisement
Guest User

Untitled

a guest
Jan 21st, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Solution {
  5.  
  6. public static void main(String[] args) {
  7. Scanner in = new Scanner(System.in);
  8. int T = in.nextInt();
  9. for (int t = 0; t < T; t++) {
  10. int N = in.nextInt();
  11. int M = in.nextInt();
  12. int a[] = new int[N];
  13. boolean reachable[] = new boolean[N];
  14.  
  15. for (int n = 0; n < N; n++) {
  16. a[n] = in.nextInt();
  17. }
  18.  
  19. if (expandReachable(a, reachable, 0, N, M))
  20. System.out.println("YES");
  21. else
  22. System.out.println("NO");
  23. }
  24. }
  25. public static boolean expandReachable(int[] a, boolean[] reachable, int i, int N, int M) {
  26. if (i >= N) {
  27. return true;
  28. }
  29.  
  30. if (i < 0)
  31. return false;
  32.  
  33. if (reachable[i] == true) {
  34. return false;
  35. }
  36.  
  37. if (a[i] == 1) {
  38. return false;
  39. }
  40.  
  41. reachable[i] = true;
  42.  
  43. if (expandReachable(a, reachable, i+1, N, M))
  44. return true;
  45.  
  46. if (expandReachable(a, reachable, i-1, N, M))
  47. return true;
  48.  
  49. if (expandReachable(a, reachable, i+M, N, M))
  50. return true;
  51.  
  52. if (expandReachable(a, reachable, i-M, N, M))
  53. return true;
  54.  
  55. return false;
  56. }
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement