Cover in Water

Problem

Filip has a row of n cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal:

1. Place water in an empty cell.
2. Remove water from a cell and place it in any other empty cell.

If at some moment cell i (2 <= i <= n-1) is empty and both cells i-1 and i+1 contain water, then it becomes filled with water automatically.

Find the minimum number of times he needs to perform action 1 in order to fill all empty cells with water. Note that you don’t need to minimize the use of action 2. Blocked cells neither contain water nor can Filip place water in them.

Input:
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#

Output:
2
2
5
0
2

Approach

We are given two options: put water in a block or take water from a block and put it in another block. Also if i - 1 and i + 1 block are filled with water then i block gets automatically filled (Minecraft infinite water mechanic). So If we can find three consecutive blocks, then we only need two blocks of water to create infinite water and that would be our solution. If we can’t find three consecutive blocks then we just need to count the number of empty blocks.

Code

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  string str;
  cin >> str;

  int cnt = 0, dot = 0;
  bool found = false;
  for (int i = 0; i < n; i++) {
    if (str[i] == '.') {
      cnt++;
      dot++;
    } else {
      if (cnt >= 3) found = true;
      cnt = 0;
    }
  }
  if (cnt >= 3) found = true;

  cout << (found ? 2 : dot) << '\n';
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

Complexity

• time: O(n) per test case — one pass over the string
• space: O(1) beyond the input string