Using Union-find algorithm:

7. Application: Chess A standoff of queens on a generalized n n chessboard is a collection of queens, where every queen in the standoff can attack some other queen in the standoff, and for every selection of a "protagonist" and an "antagonist" queen from the standoff, there is a sequence of attackson other queens which eventually leads the protagonist queen to defeat the antagonist. As an example, if we have queens in the following configuration, where "P" is a protagonist queen, "A" is an antagonist queen, and each "Q" is another queen, "P" could carry out the marked (with directional arrows) sequence of moves to attack "A". Here, the rightmost two queens do not belong to the standoff defined by the other queens, but they are in a standoff of their own. 2No positioning moves other than direct attacks are permitted. We also assume that the protagonist queen is somewhat like an anime protagonist in that the other queens are assumed to be stationary during the entire sequence of moves. Suppose that the number of queens on the board is O(n for some e (0,1) Design an algorithm which finds the largest queen standoff in O(n2) time. You may assume that the input is an n n boolean two-dimensional array where True indicates the presence of a queen, and the desired output is a list of ordered pairs (i,j) representing the positions of queens in the largest standoff. (* * )