SRM 707, D2, 250-Pointer (Cross)

James S. Plank

Sat Feb 11 14:26:46 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
The tests.sh script. MD5 hash: b4ea5b564cb64524078d23340aa1e40c
The answers.txt file. MD5 hash: fb6853a4a0b40ccbec3c2f7ca6236ca7
boards.tar: This is a tar file of the boards that the testing script uses.
Problem Given in Topcoder: January, 2017
Competitors who opened the problem: 271
Competitors who submitted a solution: 254
Number of correct solutions: 211
Accuracy (percentage correct vs those who opened): 77.9%
Average Correct Time: 13 minutes, 0 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of strings, where each string in the vector is the same size.
The vector has between 3 and 50 strings.
The strings contain between 3 and 50 characters each.
Each string is composed of the characters '.', and '#'.

The vector contains a cross if there indices i and j where:

   Element ( i-1, j   ) = '#'
   Element ( i,   j-1 ) = '#'
   Element ( i,   j   ) = '#'
   Element ( i,   j+1 ) = '#'
   Element ( i+1, j   ) = '#'

Return the string "Exist" if the vector contains a cross.

Return the string "Does not exist" if the vector does not contain a cross.

The examples

Example	Input	Answer
0	{".##", "###", "##."}	`"Exist"`
1	{".##", "###", "#.."}	`"Does not exist"`
2	{"######", "######", "######", "######", "######", "######", "######"}	`"Exist"`
3	{".#.#", "#.#.", ".#.#", "#.#."}	`"Does not exist"`
4	{".#.#", "###.", ".###", "#.#."}	`"Exist"`

Testing yourself

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

Try this on your own. If you get stuck, return here and read what I've written below.

Given row i and column j, determining whether there is a cross centered at row i and column j is a matter of testing to see whether five characters equal '#'. It's one if statement, which performs the AND of five tests. The main challenge here is to make sure that i and j are not in the first or last row/column. If they are in the first or last row/column, then they cannot center a cross, and your test might segfault (or worse yet, return a wrong answer).

So, what I did was have nested for loops, one for rows (i) and one for columns(j). Each loop starts at one instead of zero, and the termination test for i is to make sure that it is less than board.size()-1 rather than board.size(), like you usually do with a loop. The termination test for j is similar, making sure it is less than board[0].size()-1 rather than board[0].size().