VisitALot
TCO20 Round 3B · 2020-04-13 · by misof
Problem Statement
There is a R times C grid. Rows are numbered from 0 to R-1 (going north to south) and columns 0 to C-1 (going west to east). Cell in row r, column c is denoted (r, c). You start in the cell (0, 0).
There are a few obstacles (at most three of them). For each valid i, there is an obstacle in the cell (obsr[i], obsc[i]).
None of the obstacles are in cells that lie on the border of the grid.
You can travel along the grid by making steps in the four cardinal directions: 'N' (row -= 1), 'S' (row += 1), 'E' (column += 1) and 'W' (column -= 1).
Your task is to visit at least half of all cells in the grid - that is, at least R*C/2 cells, rounded up. You cannot visit the same cell twice, and you cannot visit a cell with an obstacle.
Return your sequence of movements.
Notes
- For the given constraints a solution always exists. Any valid solution will be accepted.
- The cell (0, 0) counts as visited at the beginning of your travel. Note that this means that you cannot return into this cell.
Constraints
- R will be between 2 and 50, inclusive.
- C will be between 2 and 50, inclusive.
- obsr will contain between 0 and 3 elements, inclusive.
- obsc will contain the same number of elements as obsr.
- Each element of obsr will be between 1 and R-2, inclusive.
- Each element of obsc will be between 1 and C-2, inclusive.
- Cells with obstacles will be distinct.
2
3
{}
{}
Returns: "SENE"
For a grid this small there cannot be any obstacles. The sample solution is longer than needed: it visits five of the six cells. "SE" and "EE" are two of the shortest valid solutions - each of them visits three of the six cells.
6
5
{1, 1, 4}
{1, 3, 1}
Returns: "SSEESWWSSEENEE"
The grid is shown below: 0 represents your starting spot, X are obstacles. 0.... .X.X. ..... ..... .X... ..... The path described by the example output is shown below as 0123456789ABCDE. It visits exactly half of the cells in this grid. 0.... 1X.X. 234.. 765.. 8XCDE 9AB..
2
2
{}
{}
Returns: "SEN"
3
2
{}
{}
Returns: "SSENN"
7
2
{}
{}
Returns: "SSSSSSENNNNNN"
7
8
{}
{}
Returns: "EEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEE"
The example return value shown above describes a path that visits the entire grid.
Submissions are judged against all 200 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class VisitALot with a public method string travel(int R, int C, vector<int> obsr, vector<int> obsc) · 200 test cases · 2 s / 256 MB per case