SRM 643, D2, 250-Pointer (TheKingsArmyDiv2)

James S. Plank

Wed Jan 18 13:56:49 EST 2017.
and Wed Aug 19 09:57:12 EDT 2020.

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
MD5 hash of tests.sh: 38ffbb665a3189ed67b31a3245b8e81b
MD5 hash of answers.txt: 0652c3b1427abaedff0ef700d5db94c9
Problem Given in Topcoder: December, 2014
Competitors who opened the problem: 761
Competitors who submitted a solution: 684
Number of correct solutions: 451
Accuracy (percentage correct vs those who opened): 59.26%
Average Correct Time: 15 minutes, 21 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of strings.
The vector contains between 3 and 50 elements.
Each string in the vector will contain between 3 and 50 elements.
Each string in the vector will be the same size.
Each character of each string is either an 'H' or an 'S'.
Two characters are "neighbors" if they are adjacent either horizontally or vertically.
At each point in time, if two neighbors are both 'H' characters, then at the next point in time, all of their neighbors will become 'H' characters.
Initially, you are allowed to turn any 'S' characters into 'H' characters.
Return the smallest number of 'S' characters that you will turn into 'H' characters, such that eventually, all characters will be turned into 'H' characters.

Example zero

In this example, the string is:

{ "SSSSS",
  "SSHHS",
  "SSSSS" }

The answer here is zero, because if you simply wait a few time steps, all of the characters will be turned into 'H':

  SSSSS      SSHHS      SHHHH      HHHHH
  SSHHS  ->  SHHHH  ->  HHHHH  ->  HHHHH
  SSSSS      SSHHS      SHHHH      HHHHH

The other examples

Example	Input	Answer
1	{ "SSSSS", "SSHSH", "HSSSS"}	1
2	{"SSS", "SSS", "SSS"}	2
3	{"HSHSHSH", "SSSHSSS", "SSHSHSS", "SHSHSHS"}	1
4	{"HHSH", "HHHS", "HSSS", "SHSH", "HHHS", "HSHH", "SSSH"}	0

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt

Hints

This is a problem where your input is going to fall into one of a few cases. Your job is to identify the cases, and do so in the correct order. A flow chart wouldn't hurt if you're not good at doing these things in your head.

Now, give this one a try, and if you want more help, then scroll down and read below.

From the example in the writeup, if there are two adjacent H's, either horizonally or vertically, then the whole army will eventually be happy. So, the King's goal is to make sure that there are two adjacent happy soldiers. This means that there are only three cases to care about:

If there are two adjacent H's, return 0.
Otherwise, if there is an H anywhere, return 1, because the king can simply place an H adjacent to one that's already there.
If there are no H's, then return 2, because the king needs to place two H's next to each other.

Your program simply needs to test for these cases. As I intimated above, a flow chart might be handy, especially because you can refer to it while you code. Here's my ASCII-art flow chart:

         Start
           |
           V
    |-----------|      Yes
    | Zero H's? | -------------> Return 2.
    |-----------|
           |
           | No
           V
    |---------------|
    | Two adjacent  |     Yes      
    | H's in a row? | -------------> Return 0.
    |---------------|
           |
           | No
           V
    |---------------|
    | Two adjacent  |     Yes     
    | H's in a col? | -------------> Return 0.
    |---------------|
           |
           | No
           V
        Return 1.

Here is some more detail on these steps:

Look to make sure that at least one string has an H. If not, return 2. I used a for loop and the find() method of strings to do this part.
Now, look to see if there is an "HH" in any string. Again, you can use a for loop and the find() method of strings. If you find an "HH", then return 0.
Look for two H's that are adjacent vertically. This requires a double for loop. In cases like this one, I like to start the first loop with:
for (i = 1; i < state.size(); i++) ...

Think about the reason why. Now, if you find two H's that are adjacent vertically, return 0.
If you've reached this point, then there is at least one H, but no adjacent H's. Return 1.