Goal
A strip of bushland is on fire. An aerial firefighter is dispatched to the site to put out fire using water drops.The bushland has an area of 1 x L unit length and each water drop is effective to put out fire in 3 consecutive unit cells.
For example, if a water drop is targeted at cell 4, by splash effect it will put out fire in cell 3, 4 and 5 at the same time.
_ _ _ _ _ _ _ _<br />|_|_|f|f|f|_|_|_<br /> 1 2 3 4 5 6 7 If the water drop is targeted at cell 1, fire in cell 1 and 2 will be put out.
Given the location of fire on the strip, you have to command the firefighter to put out all fire with the least number of water drops.
At this moment wind speed is very slow. You can assume the fire does not spread during your operation.
Move fast, Commander!
Line 1: N, the number of tests to follow.
The following N lines: each line is a string showing the status of each cell in a strip. The length of the line is the length of the strip.
Cells on fire are represented by 'f'. Cells without fire are represented by dots.
Output
Write N lines - for each line of input, write a number, the minimum number of water drops needed to put out all fire.
Constraints
1 ≤ N ≤ 100
1 ≤ length of each line ≤ 255
1 ≤ length of each line ≤ 255
Solution
When observing the problem, we see that we have \(2^3=8\) different patterns to handle:
...
..f
.f.
.ff
f..
f.f
ff.
fff - For ... there is nothing to do, we can skip 3 chars.
- For .ff, .f. and ..f we can't decide yet to drop water and skip the first char.
- For f.. we must drop water urgently to not forget it and skip the first char.
- For ff., f.f and fff all we can do is drop water and step ahead three chars.
Analyzing the problem further, we see that dropping water always occurs when the pattern is f.f, fff, f or ff. This idea can be formalized as regular expression / regular language with
const N = parseInt(readline());
for (let i = 0; i < N; i++) {
const drops = readline().match(/f.f|f{1,2}/g);
print(drops !== null ? drops.length : 0);
}