Connection Status:
Competition Arena > ConnectingPoints

ConnectingPoints

TCCC05 Wildcard · 2005-01-10 · by Yarin

TCCC05 Wildcard · 2005-01-10 · by Yarin · Brute Force, Greedy, Search
Class Name: ConnectingPoints
Return Type: int
Method Name: shortestWires
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

The problem statement contains an image.

In VLSI design it's important to connect certain pairs of points on a circuit using as little wire as possible. Given an empty circuit board of size N x N, we want to connect the two points A1 and A2 with each other using one wire, and the two points B1 and B2 with each other using another wire. The wires must go along the horizontal and vertical edges on the grid (see figure), and the two wires may not share a common vertex.

Create a class ConnectingPoints containing the method shortestWires, which takes an int N, the number of vertices on one side of the circuit board, and a pair of int[], X and Y, each containing four elements. Elements 0 and 1 in X and Y contain the coordinates for A1 and A2, and elements 2 and 3 in X and Y contain the coordinates for B1 and B2. The method should return the minimum length of wires needed to connect A1 with A2 and B1 with B2. If it's not possible to connect the points, return -1 (see example 1).

Constraints

  • N will be between 2 and 500, inclusive.
  • X and Y will each contain exactly four elements.
  • Each element in X and Y will be between 0 and N-1, inclusive.
  • All four coordinate pairs described by X and Y will be distinct.
Examples
0)
7
{2,5,4,4}
{1,4,5,0}
Returns: 15

This is the example in the problem statement.

1)
100
{0,99,0,99}
{0,99,99,0}
Returns: -1

The points to be connected are on the opposite corners of the circuit board, and there is no way to connect them with each other without crossing wires. Hence the method returns -1.

2)
500
{250,251,2,495}
{273,273,273,273}
Returns: 496
3)
10
{0,8,0,8}
{0,9,9,0}
Returns: -1
4)
10
{0,8,0,8}
{0,8,8,0}
Returns: 36

Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ConnectingPoints with a public method int shortestWires(int N, vector<int> X, vector<int> Y) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous