<p>You are given an <code>m x n</code> integer matrix <code>grid</code>​​​, where <code>m</code> and <code>n</code> are both <strong>even</strong> integers, and an integer <code>k</code>.</p>

<p>The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid.png" style="width: 231px; height: 258px;" /></p>

<p>A cyclic rotation of the matrix is done by cyclically rotating <strong>each layer</strong> in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the <strong>counter-clockwise</strong> direction. An example rotation is shown below:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/explanation_grid.jpg" style="width: 500px; height: 268px;" />
<p>Return <em>the matrix after applying </em><code>k</code> <em>cyclic rotations to it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/19/rod2.png" style="width: 421px; height: 191px;" />
<pre>
<strong>Input:</strong> grid = [[40,10],[30,20]], k = 1
<strong>Output:</strong> [[10,20],[40,30]]
<strong>Explanation:</strong> The figures above represent the grid at every state.
</pre>

<p><strong class="example">Example 2:</strong></p>
<strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid5.png" style="width: 231px; height: 262px;" /></strong> <strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid6.png" style="width: 231px; height: 262px;" /></strong> <strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/ringofgrid7.png" style="width: 231px; height: 262px;" /></strong>

<pre>
<strong>Input:</strong> grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
<strong>Output:</strong> [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
<strong>Explanation:</strong> The figures above represent the grid at every state.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 50</code></li>
	<li>Both <code>m</code> and <code>n</code> are <strong>even</strong> integers.</li>
	<li><code>1 &lt;= grid[i][j] &lt;=<sup> </sup>5000</code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>
class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:

        #element ordered in row manner, grouped by layer
        rows=len(grid)
        cols=len(grid[0])
        layers=min(rows//2,cols//2)
        sliced_grid=[[] for _ in range(layers)]
        for i in range(rows):
            layers_in_this_row=min(i+1,rows-i)
            for j in range(cols):
                sliced_grid[min(min(j,cols-j-1),layers_in_this_row-1)].append(grid[i][j])
        print(sliced_grid)

        #reshape layer, element ordered in clockwise manner
        reshaped=[[0 for __ in range(len(slice)) ] for slice in sliced_grid]
        for layer,layer_item in enumerate(sliced_grid):
            back_trace_id=-1
            back=True
            top_row_element_count=cols-layer*2
            for idx,item in enumerate(layer_item):
                if idx<top_row_element_count:
                    reshaped[layer][idx]=item
                elif idx<len(layer_item)-top_row_element_count and back:
                    reshaped[layer][back_trace_id]=item
                    back=not back
                    back_trace_id-=1
                elif idx<len(layer_item)-top_row_element_count and not back:                    
                    reshaped[layer][idx+back_trace_id+1]=item
                    back=not back
                else:
                    reshaped[layer][back_trace_id]=item
                    back_trace_id-=1
        print(reshaped)

        #reconstruct to traditional row format, rotate by offset
        offset=k
        reconstruct=[[0 for _ in range(cols)] for _ in range(rows)]
        offset_count=[[0,len(reshaped[layer])-1,True] for layer in range(layers)]
        for i in range(rows):
            layers_in_this_row=min(i+1,rows-i)
            for j in range(cols):
                layer=min(min(j,cols-j-1),layers_in_this_row-1)
                top_row_element_count=cols-layer*2
                if offset_count[layer][0]<top_row_element_count:
                    reconstruct[i][j]=reshaped[layer][(offset+offset_count[layer][0])%len(reshaped[layer])]
                    offset_count[layer][0]+=1
                elif offset_count[layer][0]<len(reshaped[layer])-top_row_element_count and offset_count[layer][2]:
                    reconstruct[i][j]=reshaped[layer][(offset+offset_count[layer][1])%len(reshaped[layer])]
                    offset_count[layer][0]+=1
                    offset_count[layer][1]-=1
                    offset_count[layer][2] = not offset_count[layer][2]
                elif offset_count[layer][0]<len(reshaped[layer])-top_row_element_count and not offset_count[layer][2]:   
                    reconstruct[i][j]=reshaped[layer][(offset+offset_count[layer][0]-(len(reshaped[layer])-offset_count[layer][1]-1))%len(reshaped[layer])]
                    offset_count[layer][0]+=1
                    offset_count[layer][2] = not offset_count[layer][2]
                else:             
                    reconstruct[i][j]=reshaped[layer][(offset+offset_count[layer][1])%len(reshaped[layer])]
                    offset_count[layer][1]-=1

        print(reconstruct)
        return reconstruct
154