題目描述
您正在手機上玩一款遊戲。您將會獲得一個長度為n的陣列,索引值的範圍在0到n-1之間,每個陣列中的元素為0或1。只有在索引值對應的元素為0的時候,您才能移動。
一開始您在索引0的位置,每次的移動都必須要符合以下的條件:
剛好往前跳m個索引值。
以上條件表示您每次可以從索引x移動到x+1、x-1或是x+m,且新的位置對應的元素必須要是0。當然,您無法移動到小於0的索引值。
當您移動到大於n-1的索引時,表示您贏了這場遊戲。
給定一個陣列還有跳躍的固定長度,您必須判斷出是否可以贏得這場遊戲。
原題網址
輸入格式
第一行包含一個整數T,表示測試資料的數量,範圍在1到5000之間(包含1和5000)。接下來的2T行,每兩行代表一組測試資料。
測試資料的第一行包含兩個整數n和m,n的範圍在2到100之間(包含2和100),m的範圍在0到100之間(包含0和100)。第二行包含n個用空格隔開的整數,整數的值為0或1,第一個整數的值一定是0。
輸出格式
判斷每組測試資料,如果可以贏得遊戲,輸出「YES」,否則輸出「NO」。
範例輸入
5 3
0 0 0 0 0
6 5
0 0 0 1 1 1
6 3
0 0 1 1 1 0
3 1
0 1 0
範例輸出
YES
NO
NO
額外解釋
第一組測試資料中,您可以直接從頭走到尾,通過這個陣列。
第二組測試資料中,您可以先走到索引1或2,然後再跳出來。
第三組測試資料中,就算移動到索引1的位置,也還是跳不出來。
第四組測試資料中,跳和走的距離都一樣,所以有1擋著就無法通過陣列。
解題概念
這題非常適合用遞迴來解決。可以用堆疊來嘗試所有的路線。
當目前索引值大於n-1,或是當目前索引值等於n-1且對應的整數元素為0時,表示贏得遊戲。
當索引值小於0,或是索引值對應的整數元素為1時,表示目前要走的路線行不通。
當索引值在0到n-2之間時,嘗試往後走1個索引值,或是往前走1個索引值,或是往前跳m個索引值,並將嘗試移動的結果進行OR運算,即可知道是否能找到贏得遊戲的路線。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);
final int t = sc.nextInt();
for (int i = 0; i < t; ++i) {
final int n = sc.nextInt();
final int m = sc.nextInt();
final int[] a = new int[n];
for (int j = 0; j < n; ++j) {
a[j] = sc.nextInt();
}
System.out.println(canWin(a, m, 0) ? "YES" : "NO");
}
}
private static boolean canWin(final int[] a, final int m, final int i) {
if (i >= a.length || (i == a.length - 1 && a[i] == 0)) {
return true;
} else if (i < 0 || a[i] != 0) {
return false;
} else {
a[i] = 2;
return canWin(a, m, i + 1) || canWin(a, m, i - 1) || canWin(a, m, i + m);
}
}
}