45-Degree Rotation

Time limit1sMemory limit128 MB

Summary
Rotate a character grid clockwise by a multiple of 45 degrees, including diagonal renderings, keeping letters upright and output compact.
Level

Medium6 of 10

Topics
Simulation, Matrix, Implementation
Solved
No attempts yet

Problem

You are given an R x C table filled with lowercase English letters. Print how the table looks after rotating it clockwise by K degrees.

K is a multiple of 45. The letters themselves stay upright even while the table is rotated.

Input

The first line contains two integers R and C.

Each of the next R lines contains a lowercase string of length C, representing one row of the table.

The last line contains the rotation angle K.

  • 1 <= R <= 10
  • 1 <= C <= 10
  • K is a multiple of 45 with 0 <= K <= 360.

Output

Print the appearance of the table after rotating it clockwise by K degrees.

If there are several ways to draw the rotated table, print one with the smallest possible number of lines. Preserve all leading spaces on each line, but omit trailing spaces. Every output line ends with a lowercase letter.

Examples3

  1. Example 1

    Input
    3 5
damir
marko
darko
45
    Expected output
      d
 m a
d a m
 a r i
  r k r
   k o
    o

  2. Example 2

    Input
    3 5
damir
marko
darko
90
    Expected output
    dmd
aaa
rrm
kki
oor

  3. Example 3

    Input
    5 5
abcde
bcdef
cdefg
defgh
efghi
315
    Expected output
        e
   d f
  c e g
 b d f h
a c e g i
 b d f h
  c e g
   d f
    e