504. Parking

You want to park the car guests who have come to the party, on the street. According to the rules the cars cannot park:

· In front of the private exit;

· At the bus stop and less than 10 meters before it;

· At the pedestrian crossing, and less than 5 meters before him or after him.

You made plans for the surrounding streets, smashing them into sections the length of 5 meters (this is the minimum length for parking). Land with exit on the plane is denoted by ‘D’, bus stops – ‘B’, crossings – ‘S’, others – ‘-’. Write a program that for each street will determine the number of parking spaces.

Input. The first line contains the number of streets n (1 ≤ n ≤ 100). It is followed by n lines containing street maps, each line has a length of 1 to 50 characters long and consist only of characters ‘D’, ‘B’, ‘S’ and ‘-’.

Output. For each street plan print the number of parking places.

Sample input	Sample output
3 ---B--S-D--S-- DDBDDBDDBDD --S--S--S—S--	4 0 2

SOLUTION

strings

Algorithm analysis

Iterate over all possible sections of the street of 5 meters long and check is it possible to park a car there. Let the street plan be stored in a character array s. Then it is possible to park on the section s[i] if the following conditions are simultaneously satisfied:

· s[i] = ‘-‘, the section is free;

· s[i – 1] ≠ ‘S’ and s[i + 1] ≠ ‘S’, there is no pedestrian crossing nearby;

· s[i + 1] ≠ ‘B’ and s[i + 2] ≠ ‘B’, there is no bus stop up to 10 meters ahead. Note that, according to condition of the problem, you can park right behind the bus stop;

Example

For the first example, consider all possible parking positions. They are marked in green.

Algorithm realization

Store the street plan in string s.

char s[100];

For each test case read the street plan into a character array s, starting from the first position (to simplify the processing).

scanf("%d\n",&n);

while(n--)

{

gets(s+1); res = 0;

for(i = 1; i <= strlen(s+1); i++)

For each section s[i] check is it possible to park on it.

if ((s[i] == '-') && (s[i+1] != 'S') && (s[i-1] != 'S') &&

(s[i+1] != 'B') && (s[i+2] != 'B')) res++;

Print the number of possible parking spaces on the current street.

printf("%d\n",res);

}

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

while(n-- > 0)

{

int res = 0;

char[] s = (" " + con.next() + " ").toCharArray();

for(int i = 1; i < s.length - 2; i++)

if ((s[i] == '-') && (s[i+1] != 'S') &&

(s[i-1] != 'S') && (s[i+1] != 'B') &&

(s[i+2] != 'B')) res++;

System.out.println(res);

}

con.close();

}

}