arrays - 沿一维数组移动

Question

我最近在在线编码挑战中遇到了这个问题，但我似乎无法取得任何进展。

有一个由 0 和 1 组成的一维数组。

玩家从索引 0 开始，需要超出数组的长度。

一旦超过数组的长度，玩家获胜。

玩家只能进入具有 0 的索引。

玩家可以后退 1 步、前进 1 步或前进 m 步。

问题是如何确定游戏是否可以获胜。

这一切都归结为以下函数签名:

boolean winnable(int[] arr, int m){
}

谁能帮助我开始使用算法。

稍后添加

我可以接受这个算法，当然它没有通过大多数测试用例。

public static boolean winnable(int[] arr, int m){
        int currPos = 0;
        for(int i=1; i< arr.length; i++){
            if(currPos == arr.length -1 - m) return true;
            else if(arr[i] == 0)currPos++;
            else if(arr[i] == 1){
                if(arr[currPos + m] == 0) currPos = currPos + m;
            }
        }
        return false;
    }

Answer 1

遍历整个数组。对于每个单元格-> 如果为 1，则将其标记为不可达。否则，检查它是否可达。一个单元格是可达的，如果 A)可访问之前的单元格 B) 可达之前的m个单元格。

一旦单元格被标记为可访问，您还必须将其后面所有连续的单元格标记为可访问，这些单元格都是“0”。一旦你将距离末尾少于 m 个单元格的单元格标记为可达，这意味着该端点可达。如果您已将最后 m 个单元格标记为不可到达，则末尾不可到达。