242 周赛1871 跳跃游戏7

题目链接：https://leetcode-cn.com/problems/jump-game-vii/comments/

题目描述

给你一个01串和两个整数minJump，maxJump，起始点必为0，每次能跳的步数在两个整数范围内，只能跳在0上，问能不能到达终点（字符串的最后一个字符）。

思路

bfs+剪枝，maxJump-minJump到maxJump之间的数如果有0就不用在其他范围内跳了，结果无影响，如果范围内没有0再在前面找一个可以跳的位置就行了，注意特判s.size()-1=='1'的情况

code

class Solution {
public:
    queue<int> q;
    bool canReach(string s, int minJump, int maxJump) {
    if (s[s.size() - 1] == '1') return false;
    while (q.size()) q.pop();
    q.push(0);
    while (!q.empty()) {
        int start = q.front();
        // cout << start << endl;
        if (start == s.size() - 1) return true;
        q.pop();
        int flag = 1;
        int z = max(maxJump - minJump + 1, minJump);
        for (int i = z; i <= maxJump; i++) {
            if (start + i < s.size() && s[start + i] == '0')
                q.push(start + i), flag = 0;
        }
        if (flag) {
            for (int i = z - 1; i >= minJump; i--) {
                if (start + i < s.size() && s[start + i] == '0') {
                    q.push(start + i);
                    break;
                }
            }
        }
    }
    return false;
}
};