[HackerRank]Java一維陣列(Java 1D Array)(Part 2)

題目描述

您正在手機上玩一款遊戲。您將會獲得一個長度為n的陣列，索引值的範圍在0到n-1之間，每個陣列中的元素為0或1。只有在索引值對應的元素為0的時候，您才能移動。

一開始您在索引0的位置，每次的移動都必須要符合以下的條件：

以上條件表示您每次可以從索引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」。

範例輸入

範例輸出

額外解釋

第一組測試資料中，您可以直接從頭走到尾，通過這個陣列。
第二組測試資料中，您可以先走到索引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);
        }
    }
}