TCHS-10-500

Problem Statement

There are several cannons located on a plane. Each cannon is represented as a point, and can shoot in one of four directions: left, right, up or down. Given the coordinates of the cannons, assign a direction to each one such that no cannon shoots another cannon. Cannon A shoots cannon B if and only if B is located on A's line of fire. For example, if cannon A is located at (5,7) and cannon B is located at (9,7), cannon A cannot shoot to the right and cannon B cannot shoot to the left.

You are given the coordinates of the cannons in the int[]s x and y. The i^th element of x is the x-coordinate of the i^th cannon, and the i^th element of y is the y-coordinate of the i^th cannon. Return a String where the i^th character is the direction assigned to the i^th cannon. 'L' represents left, 'R' represents right, 'D' represents down, and 'U' represents up. If there is more than one valid return string, return the one that comes first alphabetically. If there is no possible arrangement, return the empty string.

Definition

Class:	Cannons
Method:	getDirections
Parameters:	int[], int[]
Returns:	String
Method signature:	String getDirections(int[] x, int[] y)
(be sure your method is public)

Notes

-

Cannon A is located to the left(right) of the cannon B if and only if the y coordinates of A and B are equal and the x coordinate of A is less(greater) than the x coordinate of B.

-

Cannon A is located to the down(up) of the cannon B if and only if the x coordinates of A and B are equal and the y coordinate of A is less(greater) than the y coordinate of B.

Constraints

-

x will contain between 1 and 50 elements, inclusive.

-

y will contain between 1 and 50 elements, inclusive.

-

x and y will contain the same number of elements.

-

Each element of x and y will be between -1000000 and 1000000, inclusive.

-

No two cannons will be located in the same point.

Examples

0)

{1,2,2,4}

{2,1,3,2}

Returns: "DDLD"

All cannons except for the third can shoot down. The third cannon can not shoot down, but can shoot right.

1)

{0}

{0}

Returns: "D"

There is only one cannon here, so it can shoot in any direction. 'D' is chosen because it comes first alphabetically.

2)

{-3,0,9,0,0}

{0,0,0,7,-4}

Returns: ""

The second cannon is enclosed by the other cannons and cannot shoot in any of the four directions, so the empty string must be returned.

3)

{0,-4,0,5,0,-4}

{0,0,-7,3,3,3}

Returns: "RDDDUL"

4)

{-761813,348943,749420,-444982,993810,-548742,-444982,-761813,993810, 363833,728226,28752,461997,544181,776052,-761813,776052,993810,789745, 75502,348943,449038,158889,-548742,-659628,75502,363833,917729,993810, 158889,776052,728226,367390,-689680,917729,748629,367390,917729,859379, 728226}

{393728,835962,-593971,-593971,-36149,-922640,376562,-368880,-368880, -212107,-368880,-595655,-786227,393728,-463260,763742,790220,63191, -212107,-786227,-805377,-912205,-368880,883897,-912205,803745,63191, 803745,790220,-212107,-593971,939489,-912205,939489,-291544,790220, 795389,835962,795389,763742}

Returns: "LLDDLDLDDDDDDDLLURDDDDDLDLLRRLDRDDDDLRDR"

public class Cannons {

	public String getDirections(int[] x, int[] y) {
		StringBuilder buf = new StringBuilder();
		for (int i = 0; i < x.length; i++) {
			boolean d = true, l = true, r = true, u = true;
			for (int j = 0; j < x.length; j++) {
				if (i == j)
					continue;
				if (x[i] == x[j] && y[j] < y[i])
					d = false;
				if (y[i] == y[j] && x[j] < x[i])
					l = false;
				if (y[i] == y[j] && x[j] > x[i])
					r = false;
				if (x[i] == x[j] && y[j] > y[i])
					u = false;
			}
			if (d)
				buf.append('D');
			else if (l)
				buf.append('L');
			else if (r)
				buf.append('R');
			else if (u)
				buf.append('U');
			else
				return "";
		}
		return buf.toString();
	}

}