2011年9月 夏合宿3日目 Problem G: Palindrome Generator [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;
import static java.lang.Math.*;

public class Main {
  int n, m, l;
	char[][] words;
	boolean[][] map;
	V[][][] vs;

	public void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		l = 0;
		words = new char[n][];
		for (int i = 0; i < n; i++) {
			words[i] = sc.next().toCharArray();
			l = max(l, words[i].length);
		}
		map = new boolean[n + 1][n + 1];
		for (int i = 0; i <= n; i++)
			map[0][i] = map[i][0] = true;
		for (int i = 0; i < m; i++)
			map[sc.nextInt()][sc.nextInt()] = true;
		vs = new V[n + 1][n + 1][2 * l];
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				for (int k = 0; k < 2 * l; k++)
					vs[i][j][k] = new V(abs(k - l));
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				for (int k = 0; k < 2 * l; k++)
					if (k == l) {
						for (int h = 1; h <= n; h++)
							if (map[h][j])
								vs[i][j][k].add(new E(vs[i][h][k - words[h - 1].length], words[h - 1].length));
					} else if (k < l && j > 0) {
						for (int h = 1; h <= n; h++)
							label: if (map[i][h] && l - k <= words[j - 1].length) {
								int lh = words[h - 1].length;
								int ll = min(l - k, lh);
								int os = l - k;
								for (int p = 0; p < ll; p++)
									if (words[h - 1][p] != words[j - 1][os - p - 1])
										break label;
								vs[i][j][k].add(new E(vs[h][j][k + lh], lh));
							}
					} else if (k > l && i > 0) {
						for (int h = 1; h <= n; h++)
							label: if (map[h][j] && k - l <= words[i - 1].length) {
								int lh = words[h - 1].length;
								int ll = min(k - l, lh);
								int os = words[i - 1].length - k + l;
								for (int p = 0; p < ll; p++)
									if (words[h - 1][lh - p - 1] != words[i - 1][os + p])
										break label;
								vs[i][j][k].add(new E(vs[i][h][k - lh], lh));
							}
					}
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				if ((i > 0 || j > 0) && map[i][j])
					for (int k = 0; k < 2 * l; k++)
						label: if (k == l)
							vs[i][j][k].max = 0;
						else if (k < l && j > 0 && l - k <= words[j - 1].length) {
							for (int h = 0; h * 2 < l - k; h++)
								if (words[j - 1][h] != words[j - 1][l - k - h - 1])
									break label;
							vs[i][j][k].max = 0;
						} else if (k > l && i > 0 && k - l <= words[i - 1].length) {
							int li = words[i - 1].length;
							for (int h = 0; h * 2 < k - l; h++)
								if (words[i - 1][li - h - 1] != words[i - 1][li - k + l + h])
									break label;
							vs[i][j][k].max = 0;

						}
		try {
			System.out.println(max(0, dfs(vs[0][0][l])));
		} catch (NullPointerException e) {
			System.out.println(-1);
		}
	}

	private int dfs(V s) {
		Stack<V> st = new Stack<V>();
		st.push(s);
		while (!st.isEmpty()) {
			V v = st.pop();
			switch (v.s) {
			case Waiting:
				v.s = Step.Active;
				st.push(v);
				for (E e : v)
					switch (e.to.s) {
					case Waiting:
						st.push(e.to);
						break;
					case Active:
						e.to.isLoop = true;
						break;
					}
				break;
			case Active:
				v.s = Step.Inactive;
				for (E e : v)
					if (e.to.s == Step.Inactive)
						v.max = max(v.max, e.to.max + e.length);
				if (v.isLoop && v.max >= 0)
					throw null;
				break;
			}
		}
		return s.max;
	}

	private enum Step {
		Waiting, Active, Inactive
	}

	public static class V extends ArrayList<E> {
		public Step s = Step.Waiting;
		public boolean isLoop = false;
		public final int val;
		public int max = Integer.MIN_VALUE;

		public V(int val) {
			this.val = val;
		}
	}

	public static class E {
		public final V to;
		public final int length;

		public E(V to, int length) {
			this.to = to;
			this.length = length;
		}
	}

	public static void main(String... args) {
		new Main().run();
	}

	private static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}