Woburn Challenge 2018-19 Finals Round - Senior Division

Problem 2: Top Billing

Two particularly famous actors are starring in the cows' and monkeys' production: Tom Cows and Monkey Freeman. With both of them playing equally important roles, one question is at the forefront of everybody's mind: which of them will receive top billing in the credits and get to be the main face of the movie?

Tom isn't one to stand for playing second fiddle, so he's hatching a plan to discredit Monkey in the eyes of the director, Bo Vine. He's going to sneak into the main studio building in the middle of the night and rearrange its layout, in the hopes of causing Monkey to be late for the following morning's filming session. That'll show him!

The building can be represented as a grid with R rows and C columns (2 ≤ C ≤ R ≤ 100). Note that the grid has at least as many rows as it has columns. Tom will choose one starting cell (leading to the parking lot) and one different ending cell (leading to the movie set). These cells may be anywhere in the grid (not necessarily on its edges). For each remaining cell in the grid, he'll choose to either leave it vacant or obstruct it with a wall. He'll make sure that it's possible to reach the ending cell from the starting one through a sequence of horizontally/vertically adjacent vacant cells.

In the morning, Tom and Monkey will begin in the starting cell and will each attempt to make their way to the ending cell, by repeatedly moving from cell to adjacent cell (up, right, down, or left) at a rate of 1 minute per cell. Tom, having arranged the building, will follow a route allowing him to reach the ending cell as quickly as possible. Monkey, on the other hand, will follow the following procedure:

1. Make an ordered list of possible next cells to move to as follows: for each of the directions up/right/down/left (in that order), if the cell adjacent to his current one in that direction is within the grid and doesn't contain a wall, include it in the list. Note that this list will always contain between 1 and 4 cells, inclusive.
2. Move to the cell in the list which is closest to the ending cell by Manhattan distance* (ignoring any walls). If multiple cells in the list have the same minimum Manhattan distance to the ending cell, choose the one of them which appears earliest in the list.
3. If he's arrived at the ending cell, stop. Otherwise, return to Step 1.

* The Manhattan distance between a cell in (row r₁, column c₁) and another cell in (row r₂, column c₂) is defined as |r₁ − r₂| + |c₁ − c₂|.

For example, consider the following two building layouts (with "S" denoting the starting cell, "E" denoting the ending cell, and walls marked with "#"s):

...S
.##.
.##.
E...

...S
....
....
E.#.

Help Tom come up with any building layout which would cause Monkey to successfully arrive the ending cell from the starting one eventually (rather than walking around forever as in the second example above), but at least 2C − 4 minutes after Tom does. It's guaranteed that at least one such building layout exists for any valid pair of dimensions R and C (with C ≤ R).

Subtasks

In test cases worth 6/14 of the points, R ≤ 4 and C ≤ 4.

Input Format

The first and only line of input consists of two space-separated integers, R and C.

Output Format

Output R lines of C characters each, a grid representing the chosen building layout. Each character must be one of the following:

• "S": starting cell (which must appear exactly once)
• "E": ending cell (which must appear exactly once)
• ".": vacant cell
• "#": wall

Sample Input 1

4 2

Sample Output 1

[Multiple possible accepted grids]

Sample Input 2

10 9

Sample Output 2

[Multiple possible accepted grids]

Sample Explanation

In the first case, below is an example of a grid which would be accepted:

ES
..
.#
#.

For this grid, both Tom and Monkey would reach the ending cell in 1 minute, by moving to the left. This is a difference of 0, which is at least as large as the minimum required difference of 2C − 4 = 0. Therefore, this output would be judged as correct.

In the second case, below is an example of a grid which satisfies the basic output format requirements, but would not be accepted:

.........
.........
.........
.........
.........
.........
.........
....#....
.S#...#E.
.........

For this grid, Monkey would reach the ending cell in 10 minutes (following the sequence of moves ↑→→↓→→↑→→↓), while Tom would only require 8 minutes (following the sequence of moves ↓→→→→→→↑). This is a difference of 2, which is smaller than the minimum required difference of 2C − 4 = 14. Therefore, this output would be judged as incorrect. Various other grids exist which would be judged as correct, however they are not disclosed here.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 18, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)