Thanks to the rather small constraints, one simple way to approach this problem is to do recursive backtracking. You have to go to every row/column and choose whether you want to take that row/column. If you do, make sure you lock the values on that row/column so that other rows/columns can no longer use it. You can use a int/boolean array to do this part. Here is one possible implementation of the recursion.

A solution with bit manipulation is also possible. But because of the optimizations we can perform on this recursive solution, it runs almost ten times faster compared to the bit manipulation one. Consequently the bit manipulation solutions may fail to pass tests if not optimized properly.

59%
Solution Ratio

NirjhorEarliest,

user.500039Fastest, 0.0s

NirjhorLightest, 131 kB

steinumShortest, 1009B

Toph uses cookies. By continuing you agree to our Cookie Policy.