MazeConstruct
SRM 707 by Blizzard · 2016-12-07 · by cgy4ever
SRM 707 by Blizzard · 2016-12-07 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
You may have solved the following classic task before:
Given is a rectangular board divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You start in the cell (0, 0). In each step you can move to an adjacent cell (up, down, left, or right). Obviously, you may not leave the board and you may not enter a cell with an obstacle. You want to reach the cell (n-1, m-1). What is the smallest number of steps you need?
In this task, you are going to solve the above task in reverse. You are given anint k.
Design any rectangular board with the following properties:
String[] with n elements, each containing m characters.
Use the character '#' to represent an obstacle and the character '.' to represent an empty cell.
Given is a rectangular board divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You start in the cell (0, 0). In each step you can move to an adjacent cell (up, down, left, or right). Obviously, you may not leave the board and you may not enter a cell with an obstacle. You want to reach the cell (n-1, m-1). What is the smallest number of steps you need?
In this task, you are going to solve the above task in reverse. You are given an
- The number of rows (n) must be between 1 and 50, inclusive.
- The number of columns (m) must be between 1 and 50, inclusive.
- The corner cells (0, 0) and (n-1, m-1) must both be empty.
- It must be possible to reach the cell (n-1, m-1) from the cell (0, 0). Additionally, the shortest way of doing so must have exactly k steps.
Constraints
- k will be between 2 and 1,000, inclusive.
Examples
0)
3
Returns: {"...." }
There is more than one solution. Any valid solution will be accepted. For example, you may also return {"..", "..", ".."} or {"..", ".#", ".."}.
1)
4
Returns: {"...", "...", "..." }
2)
10
Returns: {"..#..", "#.#..", "..#..", ".#...", "....." }
3)
1000
Returns: {"..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", "........................................##########", "..................................................", "#################################################.", "..................................................", "..................................................", "..................................................", "#################################################.", "..................................................", "..................................................", "..................................................", "#################################################." }
4)
999
Returns: {"..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", ".#################################################", "..................................................", "#################################################.", "..................................................", "........................................##########", "..................................................", "#################################################.", "..................................................", "..................................................", "..................................................", "#################################################.", "..................................................", "..................................................", ".................................................." }
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MazeConstruct with a public method vector<string> construct(int k) · 107 test cases · 2 s / 256 MB per case