Problem Statment↵
------------------↵
↵
You're given a matrix ofN$N$ rows and M$M$ columns, and Q$Q$ queries. $(1 <= N, M, Q <= 1000) $↵
↵
For each queryQ $(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 res+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 usefult.↵
↵
thanks :-)
------------------↵
↵
You're given a matrix of
↵
For each query
Print the final matrix as res
↵
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 :-)
