UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206790#3718. 古神审判wyz_100661ms145736kbC++11532b2024-07-25 18:01:002024-07-25 20:20:59

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,d;
string s;

int bfs(int b,int e){
	queue<pair<int,int>>q;
	q.push({b,0});
	
	while(q.size()){
		if(q.front().first == e)
			return q.front().second;
		for(int i = 1; i <= d; i++){
			if(s[q.front().first+i] == '1')
				q.push({q.front().first+i,q.front().second+1});
		}
		q.pop();
	}
	return -1;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin >> n >> d >> s;
	
	cout << bfs(0,n-1);
	
	return 0;
}

Details

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

Test #1:

score: 10
Accepted
time: 289ms
memory: 113136kb

input:

93 12
111011110011011101101001001010000110101011011010100010100001010100100000000110111000100001011

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 10
Accepted
time: 2ms
memory: 3176kb

input:

93 25
110010011101100001011111000110000011110110100011011100001101111110000100000001011100101111001

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

26 3
11010011111101000000001111

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

13 4
1100011011001

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

11 4
11100010111

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

18 4
111011101000110101

output:

5

result:

ok 1 number(s): "5"

Test #7:

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

input:

50 18
11100110101000001111111001110101111110010000001101

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 10
Accepted
time: 369ms
memory: 145736kb

input:

98 12
1100111000010000010001110010101100100011111110101010001100111011011111000000101000101110111011...

output:

9

result:

ok 1 number(s): "9"

Test #9:

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

input:

87 32
110000101001110001010110110110011110110010000100101011101010000010111011001110110110111

output:

3

result:

ok 1 number(s): "3"

Test #10:

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

input:

47 20
11011010100101010010011000000001100011111110101

output:

3

result:

ok 1 number(s): "3"