Help wanted for a problem

Правка en2, от EarthMessenger, 2022-10-17 17:13:22

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 :-)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский EarthMessenger 2022-10-17 17:13:22 443 (published)
en1 Английский EarthMessenger 2022-10-17 16:59:30 370 Initial revision (saved to drafts)