CODEWITHSUNDEEP
calgorithmoptimization
scummy
scummy

Reputation: 324

Finding the numbers of square that can be formed

I've had some troubles with this problem :

"Consider a network of NxN points with integer coordinates. Some network nodes are white, some are black (the black dots will be "1" and the white dots "0"). Using network's points with the same color as corners, may be formed squares.

For a given configuration, find the number of squares that can be formed having as vertices network's points with the same number."

For example :

4 (N)

0 1 0 0

0 0 1 1

1 0 0 0

0 1 1 1

enter image description here

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

How should I approach this problem? Obviously, the brute-force will fall for most cases, so I think it isn't necessary to post the code here.

Update : I forgot to specify that

N<=50

Upvotes: 4

Views: 1720

Answers (4)

Bert te Velde
Bert te Velde

Reputation: 853

First some terminology: The grid/network runs horizontally "x" left-to-right 1..N and vertically likewise "y" top-down. The squares to be found have vertices (corners) that we number clockwise 1..4. The first such corner, which we'll call TopLeft, is the one with lowest vertical (y) value; if there are two (a non-rotated quadrangle) it is the one with the lower horizontal (x) value.

Algorithm: scan all points and try to construct a quandrangle with the given point as vertex #1, i.e. TopLeft. This results in the following pseudocode:

// 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

Upvotes: 1

John Woo
John Woo

Reputation: 446

Given two points of a square, only 3 kinds of square can be constructed as the following picture shows. And for each case, we can simply calculate the coordinates of the other two points. We can check if such points exist using map or else a simple flag table (bool exist[MAX_X][MAX_Y]) and satisfy the “same number rule” or not.

enter image description here

So just enumerate all N*N cases, and each check the 3 kinds. Overall time complexity is O(N^2*logN) using C++ STL map or O(N^2) using flag table or C++ STL unordered_map.

Upvotes: 1

Tim Biegeleisen
Tim Biegeleisen

Reputation: 520878

I will attempt to give you an algorithm which you hopefully could turn into actual C code. A brute force approach might be to do this:

  1. For every point in your set, choose another point in the set.
  2. Based on the resulting line, determine what the next perpendicular line in the square would be, and check to see if a point exists in the set matching what would be needed.
  3. If this third point (and hence second side) be found, then repeat step 2 for the the third side of the square.
  4. Finally, if three valid points be found, then see if the third point connects appropriately back to the original point. If it does, then you have a match.
  5. If during any of these steps there is a failure, then discard the first point as a candidate, and return to step 1, choosing another point. Once you have iterated over all points, you will have either found a square, or determined that none exist.

Update and Improvement:

  1. For each point in the set, compare against every other point in the set looking for two perpendicular diagonals to other points. If found, store the ids of the two points to which it connects. If not found, then permanently discard this point from your set. This step will be O(N^2) but I see no way of avoiding it.

  2. Next, iterate over the "chosen" points (i.e. those having one or more half-sqaures), and check to see if the points to which they connect also themselves connect back to another chosen point. If so, then you have found a square. The trick here is that you don't do anymore computations here. You simply iterate over the state you already have, which should be way faster than the calculations in the first step.

This approach beats the pulp out of the brute force method because it only has to calculate half-squares. Computing squares brute force is an O(N^4) affair. This approach is O(N^2) but in practice would likely be faster since the set of points would shrink as the algorithm progresses.

Upvotes: 2

a_pradhan
a_pradhan

Reputation: 3295

The diagonals of a square intersect perpendicularly and bisect each other and are of equal length. So, connect the black dots, and try for possible pairs of lines - whether they bisect at right angles. Note that you may want to assign integer coordinates and calculate the distances and point of intersection using some algebra and geometry.

Now your improvements will lie in how will you go about selecting the pair of lines from this set. You can do this by selecting only line segments having same length and no the terminal points common (which would imply same origin and arms of an angle)

Upvotes: 0

Related Questions