[Java] Wormholes

/* Use the slash-star style comments or the system won't see your
   identification information */
/*
ID: lincans1
LANG: JAVA
TASK: wormhole
*/
import java.io.*;
import java.util.*;

class Point implements Comparable<Point> {
	private int x, y;
	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public int compareTo (Point that) {
		return this.x - that.x;
	}
	public String toString() {
		return "(" + x + " " + y + ")";
	}
}

public class wormhole {
	private int N;
	private int ans;
	private int[] rightPoint;
	private boolean[] visited;

	private void swap(int[] array, int a, int b) { 
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}

	// everytime we will start from one point
	private boolean findLoop(int u, int[] map) {
		int v = map[u], p = rightPoint[v];
		if (p == -1)
			return false;
		
		if (visited[p])
			return true;
		
		// the visited point must be the +x direction
		visited[p] = true;
		boolean ans = findLoop(p, map);
		visited[p] = false;
		return ans;
	}

	// judge that if the distinct pairing is valid
	private boolean isValid(int[] array) {
		int[] map = new int[N];
		for (int i = 0, n = N / 2; i < n; i++) {
			int u = array[i * 2], v = array[i * 2 + 1];
			// if two points are on the same line
			if (rightPoint[u] == v || rightPoint[v] == u)
				return true;
			map[u] = v;
			map[v] = u;
		}
		// start from every point
		for (int i = 0; i < N; i++) {
			if (findLoop(i, map)) {
				return true;
			}
		}
		return false;
	}

	// DFS generate distinct pairings
	private void DFS(int[] array, int index) {
		if (index == N - 2) {
			if (isValid(array)) ans++;
			return;
		}
		// pair (u, v)
		int u = index, v = index + 1;
		// backtrace to create distinct pairings
		for (int i = index + 1; i < N; i++) {
			swap(array, v, i);
			DFS(array, v + 1);
			swap(array, v, i);
		}
	}
	
	// create an index map that marked every point's first right point
	private void createRightPoint (Point[] points) {
		this.rightPoint = new int[N];
		Arrays.fill(rightPoint, -1);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (points[i].getY() == points[j].getY() && points[i].getX() < points[j].getX()) {
					rightPoint[i] = j;
					break;
				}
			}
		}
	}

	public wormhole() throws IOException {
		// Use BufferedReader rather than RandomAccessFile; it's much faster
		BufferedReader f = new BufferedReader(new FileReader("wormhole.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("wormhole.out")));
		
		this.N = Integer.parseInt(f.readLine());
		Point[] points = new Point[N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(f.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			points[i] = new Point(x, y);
		}
		// points sorted by x
		Arrays.sort(points);
		createRightPoint(points);

		int[] array = new int[N];
		for (int i = 0; i < N; i++)
			array[i] = i;

		this.ans = 0;
		this.visited = new boolean[N];
		DFS(array, 0);
		out.println(ans);
		out.close();
		f.close();
	}
	
	public static void main (String [] args) throws IOException {
		new wormhole();
	}
}

本文地址：https://blog.csdn.net/weixin_41714373/article/details/112299823