題目描述

您正在手機上玩一款遊戲。您將會獲得一個長度為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」。

範例輸入

4
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
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);
        }
    }
}