DogsInAGrid
SRM 817 · 2021-10-21 · by misof
Problem Statement
A word search puzzle is a rectangular grid of letters. The goal of the puzzle is to look for words in the grid. Words can be placed in eight cardinal directions (horizontally, vertically, or diagonally).
A dog search puzzle is a word search puzzle in which each letter is 'D', 'O', or 'G'. The goal in a dog search puzzle is to find the occurrences of the word "DOG".
Below is an example of a dog search puzzle.
DGODD
OOGOG
GOGDD
The example puzzle contains four dogs: one in column 0 downwards, one in row 0 right-to-left, one on the diagonal from the top left corner, and one on the diagonal from the top right corner.
Given N, construct any dog search puzzle with at most 40 rows, at most 40 columns, and exactly N dogs.
Return the puzzle as a
Notes
- For the chosen constraints a solution always exists.
- Remember that only the letters 'D', 'O', and 'G' are allowed in the grid. Also, the grid must be rectangular and no dimension of the grid may exceed 40.
Constraints
- N will be between 0 and 2,222, inclusive.
4
Returns: {"DGODD", "OOGOG", "GOGDD" }
The returned grid is the example grid from the problem statement. We have already seen that it contains exactly four dogs, so it is one of the acceptable answers for this test case.
2
Returns: {"OOOOO", "OODOO", "ODOGO", "OOGOO", "OOOOO" }
The returned grid, formatted as a grid: {"OOOOO", "OODOO", "ODOGO", "OOGOO", "OOOOO" } One dog is in the middle column, one is in the middle row.
7
Returns: {"DOGDOGDOGDOGDOGODOG" }
0
Returns: { }
1
Returns: {"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD", "DOGOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO" }
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DogsInAGrid with a public method vector<string> construct(int N) · 116 test cases · 2 s / 256 MB per case