Problem Statment
You're given a matrix of $$$N$$$ rows and $$$M$$$ columns, and $$$Q$$$ queries. $$$(1 <= N, M, Q <= 1000)$$$
For each query $$$(x, y, c)$$$, you need to rotate clockwise the square child matrix whose upper left corner is $$$(x, y)$$$ and lower right corner is $$$(x+c-1, y+c-1)$$$.
Print the final matrix as result.
Sample
input:
4 5 3
9 9 3 4 5
5 0 2 1 3
9 3 6 4 3
5 9 3 9 0
1 3 1
2 1 2
2 2 1
output:
9 9 3 4 5
9 5 2 1 3
3 0 6 4 3
5 9 3 9 0
Obviously there is an $$$O(n^3)$$$ brute force algorithm which is not fast enough. Are there any solution faster than $$$O(n^3)$$$?
I guess the technique of dancing links may be useful.
thanks :-)
Auto comment: topic has been updated by EarthMessenger (previous revision, new revision, compare).