Search for square numbers that can be formed

Question

I had problems with this problem:

“Consider a network of NxN points with integer coordinates. Network nodes are white, some are black (black points are“ 1 ”and white points are“ 0 ”). Using network points with the same color as the corners can be formed by squares.

For this configuration, find the number of squares that can be formed having vertices of network points with the same number.

For instance:

4 (N)

0 1 0 0

0 0 1 1

1 0 0 0

0 1 1 1

It can be formed by only one square. The output will be "1".

How do I approach this problem? Obviously, brute force will fall for most cases, so I think there is no need to publish code here.

Update: I forgot to indicate that

N <= 50

Answer 1

I will try to give you an algorithm that we hope can turn into real C code. Brute force approach could do this:

• For each point in your set, select a different point in the set.
• Based on the resulting line, determine what will be the next perpendicular line in the square, and check if there is a point in the set that matches what would be needed.
• If this third point (and therefore the second side) is found, repeat step 2 for the third side of the square.
• Finally, if three valid points are found, then see if the third point connects back to the starting point. If so, then you have a match.
• If any of these steps fails, discard the first point as a candidate and return to step 1 by selecting another point. After you have repeated all the points, you will either find a square or determine that it does not exist.

Update and improvement:

• For each point in the set, compare each point in the set, looking for two perpendicular diagonals to the other points. If found, save the identifiers of the two points to which it connects. If not found, then permanently remove this point from your set. This step will be O(N^2) , but I see no way to avoid it.

• Then iterate over the “selected” points (that is, those that have one or more half-squares), and check if the points to which they are connected are connected and back to the other selected point. If so, then you have found a square. The trick here is that you no longer do the calculations here. You simply iterate over the state that you already have, which should be faster than the calculations in the first step.

This approach selects cellulose from brute force because it must calculate half-squares. The calculation of brute force is a matter of O(N^4) . This approach is O(N^2) , but in practice it is likely to be faster, since the set of points will decrease as the algorithm advances.

Answer 2

Given the two points of the square, you can build only 3 types of square, as shown in the following figure. And for each case, we can simply calculate the coordinates of two other points. We can check if such points exist using a map or just a simple flag table (bool exist [MAX_X] [MAX_Y]) and satisfy the "rule of the same number" or not.

So, just list all the N * N cases, and each will check 3 types. The overall time complexity is O (N ^ 2 * logN) using a C ++ STL card or O (N ^ 2) using a flag table or C ++ STL unordered_map.

Answer 3

First terminology: Network / network runs horizontally "x" from left to right 1..N and vertically, similar to "y" from top to bottom. The found squares have vertices (angles), which we will designate clockwise 1..4. The first such angle that we will call TopLeft is the one with the lowest vertical value (y); if there are two (non-rotating quadrangle), this is the one that has the lower horizontal (x) value.

Algorithm: scan all the points and try to build a quandrangle with the given point in the form of vertex # 1, i.e. TopLeft. This results in the following pseudo-code:

 // for each TopLeft candidate... for x1 = 1 to N-1 // TopLeft can never have x=N for y1 = 1 to N-1 // TopLeft van never have y=N // scan vertex #2 candidates... for x2 = x1+1 to N // #2 is always strictly to the right of #1 for y2 = y1 to N // #2 is never above #1 // resulting #3 coordinates x3 = x2 - (y2 - y1) if x3 < 1 then exit 'for y2' // all next y2 will also yield x3<1 y3 = y2 + (x2 - x1) if y3 > N then exit 'for y2' // all next y2 will also yield y3>N // resulting #4 x4 = x1 - (y2 - y1) if x4 < 1 then exit 'for y2' // all next y2 will also yield x4<1 y4 = y1 + (x2 - x1) if y4 > N then exit 'for x2' // all next x2 will also yield y4>N // colors ok? if grid(x1,y1)==grid(x2,y2) && grid(x1,y1)==grid(x3,y3) && grid(x1,y1)==grid(x4,y4) then // FOUND! count+=1 endif next y2 next x2 next y1 next x1 

Answer 4

The diagonals of the square intersect perpendicularly and bisect each other and have the same length. So, connect the black dots and try the possible pairs of lines - they are divided in half at right angles. Note that you can assign integer coordinates and calculate distances and intersection points using some algebra and geometry.

Now your improvements will be how you are going to select a couple of lines from this set. You can do this by selecting only linear segments with the same length and not having common terminal points (which will mean the same origin and arms at an angle)