A Spiral Walk

Interview

Time limit1sMemory limit128 MB

Summary

Fill an N by N grid with the visit order of a clockwise spiral that starts at the top-left and ends near the center.

Level: Easy3 of 10
Topics: Simulation, Matrix, Implementation
Solved: No attempts yet

Problem

The cows love to walk in their square pasture, which has sides of length $N$ ( $1 \le N \le 750$ ) and is partitioned into $N \times N$ unit squares.

Bessie has planned the longest possible walk that starts at the upper-left square and ends at the center of the pasture (or near the center when $N$ is even), passing through every square exactly once after starting.

She has chosen a clockwise spiral route (illustrated below). Write a program that prints a map showing the order in which she visits each square.

For example, for pastures of size $N=3$ and $N=4$ , the visiting orders are:

1  2  3        1  2  3  4
8  9  4       12 13 14  5
7  6  5       11 16 15  6
             10  9  8  7

Input

The first line contains a single integer $N$ .

Output

Print $N$ lines, each containing $N$ space-separated integers. Each integer is the order in which the corresponding square is visited.

Examples5

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
1 2
4 3
```
Example 3
Input
```
3
```
Expected output
```
1 2 3
8 9 4
7 6 5
```

Example 4

Input

Expected output

Example 5

Input

Expected output

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9