OJ Board

Nice problem.

There is a better way without any hashing at all (just got AC at 0.295 sec without special optimizations).

First generate all boards (do it only once), i.e. array a[51][201][201] or a[64][256][256] in my case

Then for every knight set y1=y-k*2, y2=y+k*2+1, x1=x-k*2, x2=x+k*2+1, these are [y1;y2), [x2;x2) limits for his board.

Now add control points on Y (start/stop) for each knight-board, and do same for X.

Now, sort both arrays of control points (Y points just tell if it is a start +1, or stop -1). X tells start/stop and also tells index of knight starting/stopping his board at this control absciss/ordinate. Both arrays will contain N*2 elements.

Roam through array of Y and see how many boards on Y slice are in action at given Y. When this number > 0, roam through X adding and deleting boards from doubly-linked lists as their corresponding control points appear (make sure they cross current Y slice). Now, being at some CY/CX and with linked list in according state, check if it's empty. If it is not empty, scan the square [CX;NX - NX;NY) where NX/NY are coordinates on next X/Y control points respectively (nothing happens in this sub-square - the set of boards covering it remains the same).

This way we don't check coordinates which are not needed to check and perform at O(N*log(n) + N*P) where P is the answer.

Testing that amount at Y is positive ensures that we skip empty rows without any operations. Testing that list is not empty ensures that we skip empty columns as well.