Number Tornado (APCS 2017-03 Intermediate)

Points 100 1.0s 256M

Given an N*N two-dimensional array, where N is odd, we can start from the center position and visit every array element exactly once by moving in a clockwise spiral. For the given array contents and starting direction, output the contents in the visiting order. The following example shows the visiting order for N=5 when the first step goes left:

Outputting the array contents in this order gives 9123857324243421496834621.

Similarly, if the first step goes up, the visiting order is:

Outputting the array contents in this order gives 9385732124214968346214243.

Input Format

The first line contains an integer N, where N is odd and at least 3. The second line contains an integer from 0 to 3, representing the starting direction: 0 means left, 1 means up, 2 means right, and 3 means down. Starting from the third line, there are N lines containing the array contents from top to bottom and from left to right. Each array entry is an integer from 0 to 9, and adjacent numbers on the same line are separated by a single space.

Output Format

Output the array contents in the visiting order. The answer is a continuous sequence of array entries; do not output spaces between digits. End the output with a newline.

Sample Input 1

5
0
3 4 2 1 4
4 2 3 8 9
2 1 9 5 6
4 2 3 7 8
1 2 6 4 3

Sample Output 1

9123857324243421496834621

Sample Input 2

3
1
4 1 2
3 0 5
6 7 8

Sample Output 2

012587634

Scoring

The input contains several test cases. The time limit for each test case is 1 second. Points are awarded according to the number of correctly passed test cases:

Subtask 1 is worth 20 points: 3 <= N <= 5, and the starting direction is always left.

Subtask 2 is worth 80 points: 3 <= N <= 49, with no restriction on the starting direction.

Hint: There are many ways to solve this problem. One of them is to observe each turn and the number of steps. For example, when the starting direction is left, the first few moves are: left 1, up 1, right 2, down 2, left 3, up 3, ..., until going out of bounds.

Source

APCS implementation contest, March 4, 2017, problem 3, "Number Tornado". See the official APCS past-problem PDF and ZeroJudge c292.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.