<\/span><\/h2>\n\n\n\nLet’s play a game on an array! You’re standing at index 0 <\/strong>of an n<\/strong>-element array named game<\/strong>. From some index i<\/strong>(where 0 <= i < n<\/strong>), you can perform one of the following moves:<\/p>\n\n\n\n- Move Backward: If cell i-1 <\/strong>exists and contains a 0<\/strong>, you can walk back to cell i-1<\/strong>.<\/li>
- Move Forward:
- If cell i+1 <\/strong>contains a zero, you can walk to cell i+1<\/strong>.<\/li>
- If cell i + leap <\/strong>contains a zero, you can jump to cell i + leap<\/strong>.<\/li>
- If you’re standing in cell n-1 <\/strong>or the value of i + leap >= n<\/strong>, you can walk or jump off the end of the array and win the game.<\/li><\/ul><\/li><\/ul>\n\n\n\n
In other words, you can move from index i <\/strong>to index i + 1<\/strong>, i – 1<\/strong>, or i + leap <\/strong>as long as the destination index is a cell containing a 0<\/strong>. If the destination index is greater than n-1<\/strong>, you win the game.<\/p>\n\n\n\n<\/span>Function Description<\/strong><\/span><\/h4>\n\n\n\nComplete the canWin function in the editor below.
canWin has the following parameters:<\/p>\n\n\n\n
- int leap: the size of the leap<\/li>
- int game[n]: the array to traverse<\/li><\/ul>\n\n\n\n
<\/span>Returns<\/strong><\/span><\/h4>\n\n\n\nboolean: true if the game can be won, otherwise false<\/p>\n\n\n\n
<\/span>Input format<\/strong><\/span><\/h2>\n\n\n\nThe first line contains an integer, q<\/strong>, denoting the number of queries (i.e., function calls).
The 2 . q <\/strong>subsequent lines describe each query over two lines:<\/p>\n\n\n\n- The first line contains two space-separated integers describing the respective values of n <\/strong>and leap<\/strong>.<\/li>
- The second line contains n <\/strong>space-separated binary integers (i.e., zeroes and ones) describing the respective values of game0<\/sub> , game1<\/sub>, game2<\/sub>, ….. , gamen-1<\/sub><\/strong>.<\/li><\/ol>\n\n\n\n
<\/span>Constraints<\/strong><\/span><\/h4>\n\n\n\n- 1 <= q <= 5000<\/strong><\/li>
- 2 <= n <= 100<\/strong><\/li>
- 0 <= leap <= 100<\/strong><\/li>
- It is guaranteed that the value of game[0]<\/strong> <\/em>is always 0<\/em><\/strong>.<\/li><\/ul>\n\n\n\n
<\/span>Sample Input<\/strong><\/span><\/h4>\n\n\n\n STDIN Function\n ----- --------\n 4 q = 4 (number of queries)\n 5 3 game[] size n = 5, leap = 3 (first query)\n 0 0 0 0 0 game = [0, 0, 0, 0, 0]\n 6 5 game[] size n = 6, leap = 5 (second query)\n 0 0 0 1 1 1 . . .\n 6 3\n 0 0 1 1 1 0\n 3 1\n 0 1 0<\/code><\/pre>\n\n\n\n<\/span>Sample Output<\/strong><\/span><\/h4>\n\n\n\n YES\n YES\n NO\n NO<\/code><\/pre>\n\n\n\n<\/span>Explanation<\/strong><\/span><\/h4>\n\n\n\nWe perform the following q = 4 <\/strong>queries:<\/p>\n\n\n\n- For game = [0, 0, 0, 0, 0]<\/em><\/strong> and leap = 3<\/em><\/strong>, we can walk and\/or jump to the end of the array because every cell contains a 0<\/strong>. Because we can win, we return true.<\/li>
- For game = [0, 0, 0, 1, 1, 1]<\/em><\/strong> and leap = <\/em>5<\/strong>, we can walk to the index 1 <\/strong>and then jump i + leap = 1 + 5 = 6 <\/em><\/strong>units to the end of the array. Because we can win, we return true.<\/li>
- For game = [0, 0, 1, 1, 1, 0]<\/em><\/strong> and leap = 3<\/em><\/strong>, there is no way for us to get past the three consecutive ones. Because we cannot win, we return false.<\/li>
- For game = [0, 1, 0]<\/em><\/strong> and leap = <\/em>1<\/strong>, there is no way for us to get past the one at index 1<\/strong>. Because we cannot win, we return false.<\/li><\/ol>\n\n\n\n
<\/span>Solution –<\/strong> Java 1D Array (Part 2)<\/strong><\/strong><\/span><\/h2>\n\n\n\nimport java.util.*;\n\npublic class Solution {\n\n public static boolean find_path(int leap, int[] game, int x) {\n if (x < 0) {\n return false;\n }\n\n if (x > game.length - 1) {\n return true;\n }\n\n if (game[x] != 0) {\n return false;\n }\n\n game[x] = 5;\n\n if (find_path(leap, game, x + 1)) {\n return true;\n }\n if (find_path(leap, game, x + leap)) {\n return true;\n }\n if (find_path(leap, game, x - 1)) {\n return true;\n }\n\n game[x] = 0;\n\n return false;\n }\n\n public static boolean canWin(int leap, int[] game) {\n return find_path(leap, game, 0);\n }\n\n\n public static void main(String[] args) {\n Scanner scan = new Scanner(System.in);\n int q = scan.nextInt();\n while (q-- > 0) {\n int n = scan.nextInt();\n int leap = scan.nextInt();\n \n int[] game = new int[n];\n for (int i = 0; i < n; i++) {\n game[i] = scan.nextInt();\n }\n\n System.out.println( (canWin(leap, game)) ? \"YES\" : \"NO\" );\n }\n scan.close();\n }\n}<\/pre>\n\n\n\n