UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206793#3718. 古神审判Soulmate1001ms1252kbC++11796b2024-07-25 18:07:092024-07-25 20:21:04

answer

#include <bits/stdc++.h>
using namespace std;
int f(int n, int d,string& no) 
{
    
    vector<int> j(n,INT_MAX);
    queue<int> q;
    j[0]=0;
    q.push(0);
    while (!q.empty()) 
    {
        int cur=q.front();
        q.pop();
        
        
        if (cur==n-1) 
        {
            return j[cur];
        }
        
        
        for (int i=1;i<=d;++i) 
        {
            int nxt=cur+i;
            if (nxt<n&&no[nxt]=='1'&&j[nxt]==INT_MAX) 
            {
                
                j[nxt]=j[cur]+1;
                
                q.push(nxt);
            }
        }
    }
    
    
    return -1;
}

int main() 
{
    int n,d;
    cin>>n>>d;
    string no;
    cin>>no;

    cout<<f(n,d,no)<<endl;

    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

93 12
111011110011011101101001001010000110101011011010100010100001010100100000000110111000100001011

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

93 25
110010011101100001011111000110000011110110100011011100001101111110000100000001011100101111001

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

26 3
11010011111101000000001111

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 10
Accepted
time: 1ms
memory: 1252kb

input:

13 4
1100011011001

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

11 4
11100010111

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

18 4
111011101000110101

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

50 18
11100110101000001111111001110101111110010000001101

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

98 12
1100111000010000010001110010101100100011111110101010001100111011011111000000101000101110111011...

output:

9

result:

ok 1 number(s): "9"

Test #9:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

87 32
110000101001110001010110110110011110110010000100101011101010000010111011001110110110111

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

47 20
11011010100101010010011000000001100011111110101

output:

3

result:

ok 1 number(s): "3"