POWERCAR - Car with powers

Car with Powers race track

The race track is a straight line with starting point at Track[0] and ending point at Track[n-1]. The car is initially at Track[0].

Track[i]='#' if the track has a wall at Track[i].

The car can move from Track[i] to Track[i+1] if and only if Track[i+1] is not a wall. The time taken to move from Track[i] to Track[i+1] is 1 unit.

If there is a wall at Track[i+1], you can shoot it from Track[i] if you have enough bullets in the car. Once a bullet is fired, the bullets count will decrease by 1. The time required to fire a bullet is 0.

It is also allowed to ride the car off the track. It's allowed to move from Track[i] to offTrack[i], from offTrack[i] to offTrack[i+1] and from offTrack[i] to Track[i] (if Track[i] is not a wall). The time taken for any of these steps is 2 units.

Find the fastest possible time to finish the race. Print "Impossible" if it's impossible to finish the race.

Input:

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers the length of race track n and the number of bullets the car can fire followed by a line with a string representing the Track.

Output:

For each test case, print the expected result as specified in the problem statement.

Input Constraints:

1 <= t <= 100

2 <= n <= 1000

0 <= bullets <= 1000

Track[i] ∈ {'S','E', '0', '#'}

Track[0]='S', Track[n-1]='E'

Sample Input:

10
7 3
S00000E
2 2
SE
4 1
S00E
8 1
S0000##E
8 3
S0#00#0E
7 2
S0#0##E
10 4
S00#0#0##E
5 2
S000E
7 1
S0##00E
9 0
S0000##0E

 

Sample Output:

6
1
3
13
7
12
9
4
12
15

 


Added by:cegprakash
Date:2014-03-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

hide comments
2020-04-27 11:56:35
what's the matter with the [spoiler] ???? anyway good [spoiler] problem

Last edit: 2021-01-27 14:58:24
2019-10-06 19:55:56
all you have to do is [spoiler] and [spoiler] with [spoiler] and u are all set
2019-04-19 16:40:28
@author : You don't have to [spoiler removed] because everyone else is doing it :P

Last edit: 2019-05-02 09:19:17
2017-12-28 04:50:05
@Nebojsa
[spoiler] ! :P
Good day to you!

Last edit: 2018-01-09 21:04:21
2017-02-21 14:08:37 achint mittal
Came to this question after 2 years, AC in 1 go!!! feels good!!
2016-05-26 14:12:26 ALi Ibrahim
Finally Accepted, After about 6 hours of debugging and 7 WA!!! but i really did enjoy it :D
2015-08-13 13:12:52
awesome [spoiler] problem..

Last edit: 2016-07-29 22:39:37
2015-04-02 14:57:37 :(
2nd even with cin and cout.... Awesome problem ;)
2015-03-28 17:49:59 Nebojsa
When is it impossible to finish the race?
2015-03-11 02:27:14 MaHmOuD.


Last edit: 2015-03-12 15:53:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.