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


題目描述

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

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

往前或往後移動一個索引值。
剛好往前跳m個索引值。

以上條件表示您每次可以從索引x移動到x+1、x-1或是x+m,且新的位置對應的元素必須要是0。當然,您無法移動到小於0的索引值。

當您移動到大於n-1的索引時,表示您贏了這場遊戲

給定一個陣列還有跳躍的固定長度,您必須判斷出是否可以贏得這場遊戲

原題網址

https://www.hackerrank.com/challenges/java-1d-array

輸入格式

第一行包含一個整數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運算,即可知道是否能找到贏得遊戲的路線。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章